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

 

www.acmicpc.net/problem/4485

---

BFS 등 다양하게 풀 수 있지만

최단 경로를 물어봤으니 다익스트라로 해결하였습니다.

 

(y,x)좌표 하나를 노드로 보게 되면 결국 구해야 하는 건

(0,0) 노드에서 (N-1,N-1) 노드까지의 거리입니다.

 

이 길이를 갱신해 나가는 방법은 자신와 인접한 4방향을 살펴보며 다익스트라 원리를 적용하면 됩니다.

오른쪽, 아래쪽으로만 가라는 제한조건이 없기 때문에 4방향을 다 훑으면서 최소를 찾아야 합니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ4485.java