녹색 옷 입은 애가 젤다지?

코드

[ BFS를 이용한 완전탐색 풀이 ]

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int N, cnt=0;
int board[125][125];
int cost[125][125];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    while(true)
    {
        cnt++;
        cin >> N;
        if(N == 0) break;
        for(int i=0;i<N;i++)
        {
            fill(cost[i], cost[i]+N, 1e9);
            for(int j=0;j<N;j++)
                cin >> board[i][j];
        }

        queue<pair<int,int>> q;
        q.push({0,0});
        cost[0][0] = board[0][0];
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int nr = cur.first + dr[dir];
                int nc = cur.second + dc[dir];
                if(nr<0 or nc<0 or nr>=N or nc>=N) continue;
                // 같을 때에도 continue 해줘야함 안그러면 메모리 초과!
                if(cost[nr][nc] <= cost[cur.first][cur.second] + board[nr][nc]) continue;
                cost[nr][nc] = cost[cur.first][cur.second] + board[nr][nc];
                q.push({nr,nc});
            }
        }
        cout << "Problem " << cnt << ": " << cost[N-1][N-1]<< '\n';
    }
}

[ Dijkstra 풀이 ]

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int N, cnt=0;
int board[125][125];
int dist[125][125];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    while(true)
    {
        cnt++;
        cin >> N;
        if(N == 0) break;
        for(int i=0;i<N;i++)
        {
            fill(dist[i], dist[i]+N, 1e9);
            for(int j=0;j<N;j++)
                cin >> board[i][j];
        }

        priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
        pq.push({board[0][0],{0,0}});
        dist[0][0] = board[0][0];
        while(!pq.empty())
        {
            auto cur = pq.top(); pq.pop();
            for(int dir=0;dir<4;dir++)
            {
                int nr = cur.second.first + dr[dir];
                int nc = cur.second.second + dc[dir];
                if(nr<0 or nc<0 or nr>=N or nc>=N) continue;
                // 같을 때에도 continue 해줘야함 안그러면 메모리 초과!
                int cost = dist[cur.second.first][cur.second.second] + board[nr][nc];
                if(dist[nr][nc] <= cost) continue;
                dist[nr][nc] = cost;
                pq.push({cost,{nr,nc}});
            }
        }
        cout << "Problem " << cnt << ": " << dist[N-1][N-1]<< '\n';
    }
}

• 사실 BFS풀이와 큰 차이가 없고, 어차피 중간에 끊지 않으니 걸리는 시간도 동일하다
• BFS와 비교했을 때 priority_queue를 사용한다는 것 정도가 다름