[ 백준 4485 ] 녹색 옷 입은 애가 젤다지 ? (C++)

백준의 녹색 옷 입은 애가 젤다지? (4485) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

이 문제는 (0, 0)에서 (N - 1, N - 1) 까지 갈 때, 가장 적게 잃을 수 있는 금액이 얼마인지 구해야 하는 문제이다.

즉, (0 , 0)에서 (N - 1, N - 1)까지 가는데 드는 '최소비용'을 구하면 되는 문제이다.

본인은 이 문제를 2가지 방법으로 구현해보았다.

하나는 너비우선탐색(BFS) 탐색으로 나올 수 있는 모든 경로를 탐색해보는 완전탐색으로 구현해 보았고,

두번째 방법은 다익스트라 알고리즘을 사용해서 구현해 보았다.

각 칸의 들어가는 금액은 0 이상 9이하의 숫자라고 했으므로, 양의정수만 존재한다고 이야기이고 따라서 다익스트라 알고리즘

을 이용해서 풀 수 있다 판단해서 다익스트라 알고리즘을 사용했다.

[ 완전탐색을 이용한 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 130
#define INF 987654321
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
int Visit[MAX][MAX];
bool Inp_Flag;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            Visit[i][j] = INF;
        }
    }
}
 
void Input()
{
    cin >> N;
    if (N == 0)
    {
        Inp_Flag = true;
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(0, 0));
    Visit[0][0] = MAP[0][0];
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (Visit[nx][ny] > Visit[x][y] + MAP[nx][ny])
                {
                    Visit[nx][ny] = Visit[x][y] + MAP[nx][ny];
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
    Answer = Visit[N - 1][N - 1];
}
 
void Solve()
{
    for (int T = 1; ; T++)
    {
        Initialize();
        Input();
        if (Inp_Flag == true) return;
        Solution();
 
        cout << "Problem " << T << ": " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 다익스트라를 이용한 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 130
#define INF 987654321
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
int Dist[MAX][MAX];
bool Inp_Flag;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            Dist[i][j] = INF;
        }
    }
}
 
void Input()
{
    cin >> N;
    if (N == 0)
    {
        Inp_Flag = true;
        return;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    priority_queue<pair<int, pair<int,int>>> PQ;
    PQ.push(make_pair(-MAP[0][0], make_pair(0, 0)));
    Dist[0][0] = MAP[0][0];
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int x = PQ.top().second.first;
        int y = PQ.top().second.second;
        PQ.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                int nCost = Cost + MAP[nx][ny];
                if (Dist[nx][ny] > nCost)
                {
                    Dist[nx][ny] = nCost;
                    PQ.push(make_pair(-Dist[nx][ny], make_pair(nx, ny)));
                }
            }
        }
    }
    Answer = Dist[N - 1][N - 1];
}
 
void Solve()
{
    int Tc = 1;
    for (int T = 1; ; T++)
    {
        Initialize();
        Input();
        if (Inp_Flag == true) return;
        Solution();
 
        cout << "Problem " << T << ": " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}