[백준] 16236 아기 상어

---

아기 상어가 N * N 크기의 공간을 먹이를 먹으면서 움직이는 최단 거리를 구하는 문제이다. 최단 거리를 구하는 알고리즘은 다양하게 존재하지만 이 문제는 BFS를 사용하여 해결할 수 있다.

 

파이썬의 heapq 모듈을 사용한다. heaq에는 아기 상어의 이동 횟수, 위치, 크기, 지금까지 먹은 물고기의 수가 저장된다. heapq 모듈은 가장 첫번째 원소를 기준으로 정렬하기 때문에 반드시 이동 횟수를 가장 처음에 위치해야한다.

 

먹이를 먹는 우선순위가 몇 가지 존재하는데 유의해야한다.

 

1. 가장 가까운 먹이를 우선적으로 먹는다

heapq모듈을 사용한 BFS로 자연스럽게 해결된다

 

2. 가장 가까운 먹이가 여러 마리일 경우, 가장 위쪽에 위치한 물고기를 먹는다. 또 그러한 물고기가 여러 마리인 경우 가장 왼쪽에 위치한 물고기를 먹는다.

상어는 상, 하, 좌, 우로 이동할 수 있는데, 상어의 이동 순서를 상, 좌, 나머지로 설정한다면 해결된다.

 

 

 

아기 상어의 이동과 물고기를 먹은 경우

아기 상어는 기본적으로 상, 좌, 나머지 순서로 이동한다. 이때 불필요한 이동, 즉 한 번 이동했던 위치로 다시 가지 않기 위해 visited 배열을 선언하여 이동하지 않았던 곳만 큐에 저장한다.

 

아기 상어가 물고기를 먹은 경우 해당 위치의 물고기를 0으로 하여 물고기를 지운다. 그리고 지금까지 먹은 물고기의 수와 아기 상어의 크기가 동일하다면 아기 상어의 크기를 1증가시키고, 지금까지 먹은 물고기의 수를 0으로 초기화한다.

 

또 해당 위치에서 다시 BFS를 수행해야하기 때문에 visited 배열과 이동할 위치 정보를 가지고 있는 큐를 초기화한다.

 

공간에 먹을 수 있는 물고기가 존재하지 않을 경우 종료한다.  

 

python