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

사용한 알고리즘 : 다익스트라

우선 이 문제와 같이 그래프 상에서 상하좌우 를 이동하는 경우 제가 짠 것과 같이 X 행 Y 열 이동하는 행렬을 별도로 만들어 놓고 for 구문으로 4번씩 보며 이동하면 편합니다..... ( 혹은 행열을 하나로 묶어서 [2][4] 행렬로 만들어도 편해요...)

각 위치의 도둑루피의 값을 cave[130][130] 에 저장하고 dist[130][130] 으로 [0][0]에서 각 위치까지 얼마의 값으로 갈 수 있는지 알아봤습니다.

우선 모든 dist 값을 INF 값으로 설정 후,

dist[0][0] 값을 0 으로 하고 이 위치 (0,0)을 pq(priority_queue)에 넣고 시작 합니다.

pq에서 위치의 값을 하나씩 빼내, 이 위치를 (a,b) 라 하면,

이 위치에서 이동가능한 상하좌우(X,Y) 중에서, dist[X][Y] > dist[a][b] + cave[X][Y] (도둑루피값)

인 경우 값을 최신화 하고,

최신화 된 위치를 다시 pq에 넣어 돌렸습니다.

참고로 출력이 "Problem 1: 20" 꼴인데, 띄어쓰기를 잘못하여 많이 틀렸습니다...

여러분들은 이런 실수 없으시길 바라겠습니다......