Python/BFS BOJ-16236 아기상어

Posted on | In

[Python/BFS] BOJ-16236 아기상어

📌문제링크 풀이참고

*풀이참고 링크에 들어가서 보시면됩니다.

아기상어가 물고기를 잡아먹는 시간을 계산하면된다. 조건이 까다롭다.
아래처럼 접근해보자. 2-3-4를 계속 반복하며 먹을 물고기가 없을 경우 종료하면된다.

  1. 아기상어 위치를 체크 (9 -> 0으로 변경)
  2. visited 배열, fish 배열을 초기화
  3. 동일한 거리가 떨어진 물고기 위치를 체크 (여러마리가 존재 할 수 있음)
  4. 물고기가 여러마리일 경우, 왼쪽에 있는 것을 먼저 먹고 다시 먹을 물고기를 탐색 *먹을 물고기를 찾기위해 이미 갔던 곳을 다시 방문 할 수 있다.
    visited 배열을 새 물고기를 찾을 때마다 초기화 시켜야한다.

BFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    N = int(input())
    board = [list(map(int,input().split())) for _ in range(N)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    sx,sy=0,0
    for x in range(N):
        for y in range(N):
            if board[x][y] == 9:
                board[x][y]=0
                sx,sy=x,y
                break
    size = 2
    move_num = 0
    eat = 0
    while True :
        q = deque([])
        q.append((sx,sy,0))
        visited = [[False]*N for _ in range(N)]
        flag = 1e9
        fish = []
        while q :
            x,y,count = q.popleft()
            if count > flag : # 먹을수 있는 물고기 찾고 break
                break
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 > nx or nx >= N or 0 > ny or ny >= N:
                    continue
                if board[nx][ny] > size or visited[nx][ny]:
                    continue
                if 0 < board[nx][ny] < size: # 물고기 먹는 경우
                    fish.append((nx,ny,count+1)) # 위치,거리
                    flag = count
                visited[nx][ny]=True
                q.append((nx,ny,count+1))
        if len(fish) > 0 :
            fish.sort() # 위 & 왼쪽에 있는 물고기를 0번째로 정렬
            x,y,move = fish[0][0],fish[0][1],fish[0][2]
            move_num +=move
            eat +=1
            board[x][y]=0
            if eat == size : # 물고기 2마리를 먹으면 상어크기 +1
                size +=1
                eat =0
            sx,sy =  x,y
        else:
            break
    print(move_num)