📖Problem

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

<aside> 📌 모든 지점에 대해 목표 지점(값이 2인 지점)까지의 최단 거리를 구하기

</aside>

• 조건:
  • 지도의 크기는 n x m (2 ≤ n, m ≤ 1000)
  • 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표 지점 (2는 지도에 단 하나)
  • 결과는 각 지점에서 목표 지점까지의 거리, 갈 수 없는 땅은 0, 도달할 수 없는 지점은 -1

🔍Intuition

• 알고리즘: BFS(너비 우선 탐색)
• 최단거리를 구해야 하므로 바로 BFS가 떠올랐다. BFS는 모든 간선의 가중치가 동일할 때 최단 경로를 찾는 데 적합한 알고리즘이다.

하지만 20분이 지나도 문제 풀이 아이디어가 떠오르지 않았다…

결국 정답의 힘을 받아 코드를 작성하였다.

복습 필수!!

🔍Approach

1. 세로 길이 n, 가로 길이 m, 지도 정보를 grid 리스트로 입력받는다.
2. 각 위치마다 목표지점까지 거리를 구하는 함수 find_distance_to_goal를 호출한다.
   1. 거리배열 distances을 -1로 초기화한다. (거리 정보가 없는 경우 -1로 해야 하기 때문에)
   2. grid를 순회하며 목표지점인 2와 땅이 아닌 지점 0을 찾아내어 거리 배열distances 에 해당하는 위치의 값을 0으로 설정한다.
   3. 목표지점(target_x, target_y)의 위치를 큐 queue에 첫번째 값으로 초기화한다.
   4. 상하좌우 방향 리스트 directions도 설정한다.
   5. queue에 값이 있는 동안 현재 지점을 꺼내와 상하좌우 인접한 지점이 지도 범위 안에 있고, 갈 수 있는 땅(1)이고, 아직 방문하지 않았을 경우에 인접한 지점의 거리를 현재 거리+1로 설정하고 큐에 추가한다.
   6. queue에 값이 없어질동안 e 과정을 반복하여 BFS 탐색한다
   7. 탐색이 끝나면 거리배열 distances를 반환한다.
3. distances를 한 줄에 공백을 두어 출력한다.

🚩My submission