[Python_DFS&BFS] 백준 16236번 : 아기 상어

1. 문제

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

16236번: 아기 상어

 

 

 

2. 풀이 과정

n = int(input())
graph = [[*map(int, input().split())] for _ in range(n)]

shark = 2
dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]#위왼오아

#먹을 물고기 찾기
def find(n1, n2):
  q = []
  q.append((n1, n2, 0))
  visited = [[0 for _ in range(n)] for _ in range(n)]
  visited[n1][n2] = 1

  while q:
    q.sort()
    for _ in range(len(q)):#q안에 모두 같은 거리인 좌표만 담김
      x, y, r = q.pop(0)
      if graph[x][y] != shark and graph[x][y] != 0:
        graph[x][y] = 0
        return (x, y, r)
      for i in range(4):
        nx = x + dxy[i][0]
        ny = y + dxy[i][1]
        #지나갈 수 있는 곳이면 담기
        if 0<=nx<n and 0<=ny<n and graph[nx][ny] <= shark and visited[nx][ny] == 0:
          visited[nx][ny] = 1
          q.append((nx, ny, r+1))
          
  return (-1, -1, 0)#먹을 물고기 못 찾으면

#처음 상어의 위치 찾기
def baby_shark():
  for i in range(n):
    if 9 in graph[i]:
      return (i, graph[i].index(9))

n1, n2 = baby_shark()
graph[n1][n2] = 0
result = 0
fish = 0
while True:
  #위치(x, y), 걸린 시간
  n1, n2, r = find(n1, n2)
  #먹을 물고기 못 찾음 = 종료
  if n1 == n2 == -1 :
    break
    
  result += r
  fish += 1
  #자기 크기만큼 물고기 먹으면 상어 크기 증가
  if fish == shark:
    shark += 1
    fish = 0

print(result)