백준 / 4485 / 녹색 옷 입은 애가 젤다지? / 다익스트라 알고리즘 / C++

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

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

출발점에서 인접한 방향(상,하,좌,우)으로 이동하면서 도착지점까지 가장 적은 루피손실을 만들어내는 문제였습니다.

BFS로도 풀 수 있겠지만, 다익스트라 알고리즘으로 풀어보았습니다.

다익스트라 알고리즘 문제는 아직 경험치가 부족해서 풀다보니 BFS랑 다익스트라를 합친 것 같은 .. 혼종 알고리즘이 되어버렸지만 ... 그래도 출력은 잘되고 채점은 맞았다고 나왔습니다 !

 

완벽하게 다익스트라 알고리즘을 구현했다면 이동할때마다 그 좌표를 지나갈 때, 잃게되는 루피로 배열을 갱신시키는 새로운 배열을 하나 더 만들어서 좌표에 맞게 값을 갱신시켜서 마지막 도착점에서의 값을 출력하면 됩니다. 제 블로그 이전글에 보면 BFS문제풀이를 하는데 큐에 중복된 값이 들어가다 보면 메모리 초과가 나서 이 문제를 풀때에도 visited배열로 방문체크를 미리 해서 중복되지 않게 풀었는데 ( 우선순위 큐에 좌표와 값을 넣고 루피감소 최소값의 루트를 자연스레 이동하다보니 다른 곳을 먼저 이동하는 루트에서 답이 나올수 없는 구조라 중복되는 좌표는 건너뛰어도 문제가 없었습니다) , 다익스트라로 풀이를 하신 다른분들의 풀이를 보니 따로 방문체크를 안하셨는데도 다들 맞으신것을 보니 여기서는 메모리초과 문제가 발생하지 않는 것 같습니다. (그래서 따로 기준이 안세워지니 더욱 어렵네요 ㅜㅜ) 

 

★ 틀린 부분이 있을 수 있습니다 ! 댓글로 수정해 주시면 정말 감사하겠습니다 ! 또한, 궁금하신 부분은 댓글 남겨주시면 제가 알려드릴 수 있는 부분에 대해서는 친절히 알려드리겠습니다.

 

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int N;
int arr[125][125];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[125][125] = { false };
static int counting = 1;
 
 
void dijkstra(int x,int y)
{
    priority_queue<pair<int, pair<int, int>>> PQ;
    visited[x][y] = true;
    int cost = arr[x][y];
    PQ.push(make_pair(-cost,make_pair(x,y))); // 우선순위큐가 디폴트로 내림차순이라 최소값을 만들기위해 -를 붙여서 push합니다
    
 
    while (!PQ.empty())
    {
        int noWDistance = -PQ.top().first;
        auto cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < 4; i++)
        {
            
            int newX = cur.first + dx[i];
            int newY = cur.second + dy[i];
 
            if (newX >= 0 && newX < N && newY >= 0 && newY < N && visited[newX][newY] == false)
            {
                int newDistance = arr[newX][newY] + noWDistance;
                PQ.push(make_pair(-newDistance, make_pair(newX, newY)));
                visited[newX][newY] = true;
 
                if (newX == N-1 && newY == N-1)
                {
                    cout << "Problem " << counting << ": " << newDistance << endl;
                }
            }
 
            
        }
        
    }
 
 
}
 
 
int main()
{
    
    
    while (true)
    {
        cin >> N;
        if (N == 0)
            break;
        else
        {            
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    cin >> arr[i][j];
                }
            }
 
            dijkstra(0,0);
 
            counting++;
 
            for (int i = 0; i < N; i++) //새롭게 입력을 받아오기 때문에 이전에 방문체크를 한 visited배열을 다시 false로 밀어줍니다.
            {
                for (int j = 0; j < N; j++)
                {
                    if (visited[i][j] == true)
                        visited[i][j] = false;
                }
            }
        }
 
        
    }
 
 
    return 0;
 
    
}