[BOJ 4485 // C++] 녹색 옷 입은 애가 젤다지?

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 4485번 문제인 녹색 옷 입은 애가 젤다지?이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/4485

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

이 문제에서는 주어진 2차원 배열에서 지나가는 칸의 수의 합이 최소가 되는 경로를 찾는 문제이다.

이 문제는 2차원 배열 모양의 그래프에서 최단거리가 되는 경로를 찾는 문제로 볼 수 있으므로, dijkstra 알고리즘을 사용하면 간단히 문제를 풀 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
using std::cin; using std::cout;
using std::pair;
using std::priority_queue;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int num = 0;

void solve(int N) {
    int cave[125][125];
    bool visited[125][125];
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            int temp; cin >> temp;
            cave[i][j] = temp;
            visited[i][j] = false;
        }
    }
    priority_queue<pair<int, pair<int,int>>> pq; // {dist,{row,column}}
    pair<int, int> pair00 = { 0,0 };
    pair<int, int> pairnn = { N - 1,N - 1 };
    pq.push({ -cave[0][0],pair00 });
    pair<int, int> current = { 0,0 };
    while (!pq.empty()) {
        current = pq.top().second;
        int dist = -pq.top().first; pq.pop();
        if (visited[current.first][current.second]) continue;
        if (current.first == N - 1 and current.second == N - 1) {
            cout << "Problem " << num << ": " << dist << '\n';
            break;
        }
        visited[current.first][current.second] = 1;
        for (int i = 0;i < 4;i++) {
            int rr = current.first + dr[i];
            int cc = current.second + dc[i];
            if (0 <= rr && rr < N && 0 <= cc && cc < N) {
                if (!visited[rr][cc]) {
                    pq.push({ -dist - cave[rr][cc],{rr,cc} });
                }
            }
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    while (N != 0) {
        num++;
        solve(N);
        cin >> N;
    }
    return 0;
}