[파이썬] 백준 16236번 - 아기 상어 풀이

https://www.acmicpc.net/problem16236
티어: 골드 3

 

로직

먼저, bfs를 이용해 가장 가깝고 먹을 수 있는 물고기를 구하는 함수를 생각해봅시다.
함수의 로직은 대략적으로 다음과 같습니다.
 
1. 함수 파라미터로 아기상어의 현재 좌표와 크기를 가져옵니다.
2. deque를 만들고, (x좌표, y좌표, 0)인 튜플을 덱에 넣습니다.
    여기서 0은 이동 거리입니다.
3. 정점을 방문했는지 확인하는 visited 2차원 배열을 생성합니다.
4. 물고기에 도달했는지 여부를 나타내며, 가장 가까운 물고기의 거리를 나타내는 m 변수와, 찾은 가까운 물고기들의 좌표를 담을 배열 fishes를 생성합니다.
5. 덱이 비어있지 않은 동안, 6번부터 9번을 계속 반복합니다.
6. 덱의 popleft 함수로 가장 앞에 있는 값을 빼오고, 각각 x, y, dist 라는 변수에 저장합니다.
7. x, y로 표현된 좌표의 상하좌우 칸을 조사하고 nx, ny라는 변수에 넣습니다. 좌표가 올바르고, 방문한 적이 있다면 8~9번을 수행합니다.
8. 좌표가 있는 칸이 0 또는 상어의 크기와 같다면 (통과 가능) 덱에 (nx, ny, dist + 1)을 넣고 visited[ny][nx] 값을 True로 설정합니다.
9. 좌표가 있는 칸이 1~상어의 크기 사이라면 (먹기 가능) m이 초기값인 -1인지 조사하고, 맞다면 m에 dist + 1값을 넣습니다 fishes 배열에 (nx, ny, dist + 1) 값을 추가합니다. 아니라면, m이 dist + 1값과 같은지 검사하고 같다면 fishes 배열에 (nx, ny, dist + 1) 값을 추가합니다.
10. fishes 배열에 값이 있다면 그중 문제에서 말한대로 가장 위, 가장 왼쪽 순서로 정렬해 가장 왼쪽, 위에 있는 물고기의 좌표와 이동한 거리를 반환합니다.
11. fishes 배열이 비어있다면 -1을 반환합니다.
 
이제, 함수의 반환값이 -1이 아닌동안 계속해서 함수를 반복하고 time에 이동한 거리를 더합니다.
마지막으로 time을 출력해주면 됩니다.