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

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

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

DFS, DP 방법을 시도하였으나 결국엔 다익스트라로 풀면 깔끔한 문제이다.

참고로 DFS로 풀면 시간 초과가 발생한다..ㅠ

다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로서, 이 문제 또한 출발점이 [0][0]인 하나로 지정되어있기에 가능한 풀이이다.

대신 기존의 풀이방식과 달라서 처음부터 다익스트라로 푸는 것을 떠오르지 못했다.

왜냐하면 2차원의 dist 배열을 가져야 하기 때문이다.

 

🚨 추가적인 주의점

- dist 배열을 갱신할 때 현재의 dist 배열 값을 활용한다. 

 

struct Cave {
    int r;
    int c;
    int d;
};

...
int br = q.front().r;
int bc = q.front().c;
int bd = q.front().d;

if(inside(nr, nc, n) && dist[nr][nc] > bd + caves[nr][nc]) {
    dist[nr][nc] = bd + caves[nr][nc];
    q.push(Cave({nr, nc, dist[nr][nc]}));
}

처음에 Queue를 세팅할 때 row, column, 그리고 그 때의 최소 거리를 같이 저장하도록 했는데, 그럴 필요가 없었다.

이렇게 되면 불필요하게 과거의 기록이 Queue에 쌓이면서 반복적으로 참고하므로 정답까지의 갱신이 느려진다.

그래서 이를 개선하자 급격하게 메모리와 실행 시간이 절약되었다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int caves[125][125] = {0};
int dist[125][125] = {0};
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

struct Cave {
    int r;
    int c;
};

queue<Cave> q;

bool inside(int r, int c, int n) {
    return r >= 0 && r < n && c >= 0 && c < n;
}
int main(void) {
    int n = 1;
    int num = 1;
    while(true) {
        cin >> n;
        if(n == 0) {
            break;
        }
        
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                cin >> caves[i][j];
            }
        }
        
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                dist[i][j] = 125 * 125 * 10;
            }
        }
    
        dist[0][0] = caves[0][0];
        q.push(Cave({0,0}));
        
        while(!q.empty()) {
            int br = q.front().r;
            int bc = q.front().c;

            q.pop();
            
            for(int d = 0;d < 4;d++) {
                int nr = br + dr[d];
                int nc = bc + dc[d];
                
                if(inside(nr, nc, n) && dist[nr][nc] > dist[br][bc] + caves[nr][nc]) {
                    dist[nr][nc] = dist[br][bc] + caves[nr][nc];
                    q.push(Cave({nr, nc}));
                }
            }
            
        }
        
        printf("Problem %d: %d\n", num, dist[n - 1][n - 1]);
        num++;
    }
}

앞으로도 한 정점에서 다른 정점까지의 최단거리를 구할 때는 다시 한 번 다익스트라를 우선적으로 고려해보기로~