백준 14940 - 쉬운 최단거리

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

14940번: 쉬운 최단거리

BFS가 어떻게 진행되는 지 이해해야 풀 수 있는 문제

 

목표지점까지의 최단 거리를 구하기 위해, 각 지점에서 매번 일반적인 BFS를 수행하게 되면 BFS를 N^2번 수행해야 하므로 시간이 너무 오래 소요된다. 역으로 BFS를 목표지점에서 시작하면 한 번의 BFS로 모든 지점까지의 거리를 계산할 수 있다.

 

여기까지는 처음 문제를 보자마자 감이 왔는데, 거리 계산을 구현하는 데 애를 먹었다. 고생 끝에 내가 찾은 해답은 다음과 같다. (별거 없긴 함)

 

동적계획법의 아이디어를 활용한다. 그래프 탐색은 항상 인접한 지점끼리 이뤄지므로, 시작 지점에서 현재 지점까지의 거리를 k라고 하면, 현재 지점에서 BFS를 통해 발견한 새 지점까지의 거리는 반드시 k+1이다.

 

따라서 일반적인 BFS 코드에서 visited 배열 값 계산만 다음과 같이 구현하면 문제를 해결할 수 있다.

visited[next_row][next_col] = visited[cur_pos.row][cur_pos.col] + 1;

이 방법은 다른 그래프 탐색 문제에서도 자주 사용될 거 같아 익혀두면 좋을 듯 싶다.

 

배운 내용

2차원 vector 초기화

vector 생성자 ( vector (배열 크기, 초기값) )를 이용한다.

ex) vector arr(row, vector (col, 0)