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

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

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

 

#include <iostream>
#include <queue>

struct Edge {int x,y,w;
    bool operator<(const Edge& a) const { return w > a.w; } // Edge 크기 비교는 가중치로
    Edge() = default;
    Edge(int x, int y, int w) : x(x),y(y),w(w) {}
};
int N, dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};
using namespace std;

bool bound(Edge a) {return a.x>=0&&a.x<N&&a.y>=0&&a.y<N;}
int bfs(int G[][125], int d[][125]) {
    priority_queue<Edge> PQ;
    d[0][0] = 0; // 시작 정점까지의 거리를 0으로
    PQ.push({0,0,0});
    while(!PQ.empty()) {
        Edge u = PQ.top();
        PQ.pop();
        if(d[u.y][u.x] < u.w) continue; 
        // 시작 정점에서 방문하는 정점까지의 거리가 인접한 정점에서 방문하는 거리보다 작으면 업데이트 x
        for(int i=0;i<4;++i) { // 인접한 정점까지의 거리 업데이트
            int nx = u.x + dx[i], ny = u.y + dy[i];
            Edge adj = {nx,ny,G[nx][ny] + u.w};
            if(adj.x == N-1 && adj.y == N-1) return adj.w; // 도착지를 만나면 도착지 까지의 거리 반환
            if(bound(adj)&&d[ny][nx] > adj.w) {
                d[ny][nx] = adj.w;
                PQ.push(adj);
            }
        }
    }
}

int main() {
    int G[125][125], d[125][125];
    int T = 0;
    while(1) {
        scanf("%d",&N);
        if(N==0) break;
        for(int i=0;i<N;++i) {
            for(int j=0;j<N;++j) {
                scanf("%d",&G[i][j]);
                d[i][j] = INT32_MAX;
            }
        }
        printf("Problem %d: %d\n",++T,bfs(G,d)+G[0][0]);
    }
}

문제 분류는 다익스트라였기에 다익스트라로 시작했지만, 사실 우선순위 큐를 사용한 bfs로 문제를 해결했다.

 

문제에서 주어진 TC들을 수행한 후 d(거리)배열 출력 결과를 살펴보니 모든 정점에 대한 거리 업데이트가 이루어지지 않은 채 종료된 경우가 많았는데 priority queue의 이용과 (N-1,N-1)을 만나면 조기 종료하도록 작성했기 때문으로 보인다.

 

•  N = 3                      

0	3	6
5	12	8
9	INF	15

 

•           N = 4

0	2	3	12	INF
7	10	5	13	INF
8	6	6	15	INF
8	15	14	INF	INF
9	10	11	11	16