[4485] 녹색 옷 입은 애가 젤다지?

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

4485번: 녹색 옷 입은 애가 젤다지?

다익스트라 알고리즘으로 접근한 문제다.

 

풀이

너비우선탐색을 수행한다. 다익스트라 알고리즘의 특성상 우선순위 큐를 사용해서 풀어야 하지만, 문제의 N값이 크지 않기에 배열을 정렬하여 풀어도 시간초과는 피할 수 있다. 스위프트의 경우 우선순위큐를 직접 구현해야하기에 귀찮다.

 

방문여부를 저장할 2차원 visited 배열, 각 좌표에 도둑루피의 값을 담을 2차원 map 배열과 해당좌표까지의 최저 cost를 담을 2차원 cost배열을 생성한다. cost 배열은 INF로 초기화한 뒤 탐색을 수행한다. 

 

x, y, cost 정보를 담아낼 배열을 생성한다. 배열에서 cost가 가장 작은 좌표를 먼저 방문하여 (현재 좌표의 cost + 인접배열의 cost값)을 계산하여 인접배열의 cost를 더 작은 값으로 갱신한다. 다음 탐색에 cost가 가장 작은 값을 방문해야 하니 매 반복문의 마지막에는 큐를 정렬해 준다.

 

탐색이 끝나면 목적지인 cost배열의 가장 마지막 값을 출력하면 된다.

 

map 배열을 통해 cost배열의 시작점의 비용을 초기화

초록색은 현재 탐색위치, 빨간색은 큐에 담긴 좌표들이다. map배열의 값과 cost값을 사용하여 인접 배열의 값을 더 작은 값으로 갱신한다.

마지막 좌표 값이 구해지더라도 방문하지 않은 나머지 값들로 갱신될 수 있으므로 cost가 작은 순으로 탐색을 마저 수행한다.

정답 코드