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

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

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

오랜만에 머리쓰는 문제를 풀었습니다..

처음엔 BFS로 접근해서 답은 맞췄지만 시간복잡도를 줄이기 위해 다른 방법을 더 고민해보았습니다.

먼저 DP로 접근해보았는데 4방향 모두 이동 가능해서인지 원하는 답이 안나왔습니다 .ㅠㅠ

그 후 Dijkstra 로 접근해서 풀이한 결과, 시간 복잡도를 일반 BFS의 절반으로 줄일 수 있었습니다.

소스코드는 BFS , Dijkstra 버전 둘 다 첨부하였습니다!

---

C++ 소스 코드

<Dijkstra>

#include <iostream>
#include <queue>
#define MAX 126
#define INF 987654321
using namespace std; 
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
struct pos {
    int c, x, y;
    bool operator < (pos a)const { return c > a.c; }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,maps[MAX][MAX],costs[MAX][MAX];
    for(int t=1;;t++){
        cin >> n;
        if (n == 0) break;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin >> maps[i][j];
            }
            fill(&costs[0][0], &costs[n][n]+1, INF);
            costs[0][0] = maps[0][0];
            priority_queue<pos> pq;
            pq.push({maps[0][0],0,0});
            while(!pq.empty()){
                int x = pq.top().x, y = pq.top().y;
                int c = pq.top().c;
                pq.pop();
                if(c > costs[x][y]) continue;
                for(int i=0;i<4;i++){
                    int nx = x +dx[i], ny = y+dy[i];
                    if(nx < 0 || nx >= n || ny <0 || ny >=n) continue;
                    if(costs[nx][ny] > c + maps[nx][ny]){
                        costs[nx][ny] = costs[x][y] + maps[nx][ny];
                        pq.push({costs[nx][ny],nx,ny});
                    }
                }
                
            }
        }
        cout << "Problem "<< t <<": "<< costs[n-1][n-1] << '\n';
    }
    return 0;
}

<BFS>

#include <iostream>
#include <queue>
#define MAX 126
#define INF 987654321
using namespace std;
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,maps[MAX][MAX],costs[MAX][MAX];
    for(int t=1;;t++){
        cin >> n;
        if (n == 0) break;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin >> maps[i][j];
            }
            fill(&costs[0][0], &costs[n][n]+1, INF);
            costs[0][0] = maps[0][0];
            queue<pair<int, int> > q;
            q.push(make_pair(0,0));
            while(!q.empty()){
                int x = q.front().first, y = q.front().second;
                q.pop();
                for(int i=0;i<4;i++){
                    int nx = x +dx[i], ny = y+dy[i];
                    if(nx < 0 || nx >= n || ny <0 || ny >=n) continue;
                    if(costs[nx][ny] > costs[x][y] + maps[nx][ny]){
                        costs[nx][ny] = costs[x][y] + maps[nx][ny];
                        q.push(make_pair(nx,ny));
                    }
                }
                
            }
        }
        cout << "Problem "<< t <<": "<< costs[n-1][n-1] << '\n';
    }
    return 0;
}