[백준 알고리즘][다익스트라] 4485번 녹색 옷 입은애가 젤다지?

문제 정의

N*N의 동굴의 [0][0]번 칸에서 시작해서 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 칸마다 도둑루피가 있는데, 도둑루피의 크기만큼 소지금을 잃게 되는데 최소한의 금액을 잃으며 동굴 건너편까지 이동을 해야 한다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/4485)

문제 풀이

최단경로 문제에서는 다익스트라 알고리즘을 그대로 따라 해보는 정도였다면 이 문제는 다익스트라를 이용해서 어떻게 최단 경로를 구할 수 있는지를 생각해볼 수 있다. 다익스트라에서 한 정점에서 다른 정점으로의 최단거리를 구할 때 cost를 비교하여서 구했다. 이 문제에서는 최소한의 금액을 잃으며 이동해야하므로 다음 칸의 도둑루피의 크기만큼이 그 칸으로 이동하기 위한 cost라고 생각을 하면된다. 동굴의 각 칸에서 갈 수 있는 칸은 상하좌우 총 4곳이고, 각 칸에는 도둑루피의 크기가 주어져있다. 나머지 다른 칸으로 이동하기 위해서는 cost가 무한대라고 생각을 하면 그 칸으로 이동하지 않을 것이다. 칸을 이동할 때마다 새로운 칸의 좌표와 그 칸까지 오는데 잃은 루피를 우선순위 큐에 넣으면 된다. 최소로 잃어야하기때문에 우선순위 큐에서 가장 작은 루피를 반환하고, [N-1][N-1]에 도착했을 때의 잃은 루피를 출력하면 된다. 이 문제를 통해서 새로 생각해보고 알아본 부분은 큐에 넣을 때 칸의 좌표와 잃은 루피 총 3가지의 정보를 함께 묶어서 좌표에 넣어야 한다는 것이다. 이전이었다면 구조체를 사용했겠지만 c++에서는 어떤 것이 있는지를 찾아봤다. C언어에서는 struct를 사용하고 C++에서는 class를 사용한다. 구조체와 클래스 둘 다 연관 있는 데이터를 묶을 수 있다는 공통점이 있지만, 클래스 안에서는 추가적으로 함수 선언 및 정의, 생성자 및 소멸자, 상속 구조를 사용할 수 있다. 그래서 이 문제의 우선순위 큐에는 클래스를 이용해서 풀어봐야겠다. 코드를 작성하면서 막힌부분은 인접 리스트를 어떻게 만들지이다. 한 칸에서 이동할 수 있는 칸은 상하좌우 4칸인데 하나의 입력이 들어올 때 그 4칸을 전부 인접 리스트로 만드는 것이 맞는지 모르겠다. 만약 그렇게 해야 한다면 총 N*N의 리스트를 만들어야 하므로 비효율적이다! 각 칸의 도둑루피를 저장할 수 있도록 행렬을 만든 다음 우선순위 큐에서 하나씩 pop할 때마다 상하좌우를 봐주고 현재 칸에서의 cost+상하좌우칸의 cost를 해주어서 [N-1][N-1]칸까지 갈 수 있도록 한다. [N-1][N이-1]칸에 도착을 하면 최소 비용을 출력하고 break한다!

*priority_queue 에서 클래스를 큐의 멤버로 사용한다면 int 나 pair를 사용할 때와는 다르게 어떤 변수를 통해서 우선순위를 정해야 하는지 모르기 때문에 함수를 따로 선언해주지 않으면 에러가 나서 컴파일되지 않는다.

*visited 배열을 만들어서 갔던 칸을 체크해주었다. 그렇게 하지 않으니까 지나갔던 칸도 다시 지나가면서 큐에 들어가기때문에 다음 테스트케이스를 위해서 큐를 비우는데 시간이 너무나도 오래 걸렸다.