[ 백준 ][ 골드3 ] 163236번 - 아기 상어 ( 파이썬 Python )

링크 : https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

코드

---

from collections import deque

n = int(input())
sx,sy = -1,-1
graph = []
eat_cnt, fish_cnt, time, size = 0, 0, 0, 2
dx,dy = [-1,0,0,1],[0,-1,1,0]

for i in range(n):
    l = list(map(int,input().split()))
    for j in range(n):
        if l[j] == 9:
            sx,sy = i,j
        elif l[j] > 0:
            fish_cnt += 1
    graph.append(l)
    
graph[sx][sy] = 0

def BFS(x,y):
    Q = deque([(x,y,0)])
    dist_list = []
    visit = [[False] * n for _ in range(n)]
    visit[x][y] = True
    min_dist = 1e9
    while Q:
        x,y,dist = Q.popleft()
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visit[nx][ny]:
                if graph[nx][ny] <= size:
                    visit[nx][ny] = True
                    if 0 < graph[nx][ny] < size:
                        min_dist = dist
                        dist_list.append((dist+1,nx,ny))
                    elif dist+1 <= min_dist:
                        Q.append((nx,ny,dist+1))
    return sorted(dist_list)[0] if dist_list else False

while fish_cnt:
    res = BFS(sx,sy)

    if not res:
        break

    sx,sy = res[1],res[2]
    graph[sx][sy] = 0

    time += res[0]

    eat_cnt += 1
    fish_cnt -= 1

    if size == eat_cnt:
        size += 1
        eat_cnt = 0

print(time)

 

풀이

---

처음에는 한 번의 BFS안에서 모든 물고기를 찾아내고 싶었다. 탐색하는 방향을 위, 왼쪽, 오른쪽, 아래 순으로 설정하게 되면 먼저 탐색하는 방향이 문제에서 제시한 조건과 일치하기 때문에 정답을 구할 수 있을 것 같았다.

하지만 이렇게 하면 방문처리를 하기가 애매했다. 상황에따라 어떤 칸은 방문했더라도 또 방문하게 되는데 이 방문처리를 해결할 방법이 없었다.

 

따라서 한 번의 BFS에서는 해결할 수 없다고 생각했고 한 번 BFS할 때마다 가장 가까운 물고기 한 마리를 찾는 방식으로 변경했다.

BFS의 특성상 처음 방문한 노드는 그 당시가 최단거리이다. 위치를 옮길 때마다 BFS로 모든 물고기의 최단거리를 계산한 후 그 중 조건에 맞는 가장 가까운 물고기로 이동한다. 이동한 후에는 그 칸을 0으로 바꿔주고 내가 앞으로 찾을 수 있는 물고기의 개수도 바꿔준다.

만약 앞으로 이동할 수 있는 물고기칸이 없다면 지금까지의 시간을 출력한다.