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

백준 4485번

8일차 챌린지 문제인 녹색 옷 입은 애가 젤다지? 문제이다

사실 문제 제목과 문제 풀이는 상관이 없다

문제는 N * N 배열이 주어지고 각 인덱스가 의미하는 것은 1 ~ 9 까지의 정수이다. (0, 0)부터 시작해 (N - 1, N - 1) 위치까지 이동하면서 점수를 가장 적게 먹어야 한다

정리

무한 루프를 돌면서 N을 입력받고 0이면 종료한다. N을 입력받으면 이차원 배열을 채워나간다

익숙한 그래프문제이므로 푸는 방법은 여러가지가 있는데 나는 다익스트라 알고리즘을 선택했다. 다익스트라 알고리즘은 시작 노드부터 도착 노드까지 최소의 비용으로 이동할 수 있는 알고리즘이니 (0, 0)부터 시작해 숫자를 조금만 먹으며 (N - 1, N - 1)까지 도착하는 문제이다

그래서 다른 다익스트라 알고리즘처럼 dist 배열을 이용해 (i, j)로의 거리를 저장하고 우선순위 큐를 통해 문제를 해결한다

이때까지 다익스트라를 쓸 때는 일차원에서 i번 노드에서 j번 노드로 갔지만 이번에는 이차원 배열이므로 우선순위 큐가 저장할 데이터를 pair<int, pair<int, int>>로 선언했다. 첫 번째는 거리이고 두 번째는 좌표이다

처음 우선순위 큐에 (0, 0)의 값과 (0, 0) 좌표를 추가하고 우선순위 큐가 빌 때까지 반복문을 돌린다. 반복문 안에서 현재 위치와 거리를 가져오고 방향 벡터를 이용해 다음 갈 수 있는 곳을 큐에 추가한 뒤 거리가 가장 적게 걸리는 곳으로 이동을 진행한다

다음 좌표까지의 거리가 현재 저장된 거리보다 작다면 배열을 업데이트한다

코드

#include <bits/stdc++.h>
using namespace std;

int N;
int arr[126][126];

int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int index = 1;

    while (true)
    {
        cin >> N;

        if (N == 0)
            break;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cin >> arr[i][j];
            }
        }

        vector<vector<int>> dist(N, vector<int>(N, 0));

        for (int i = 0; i < N; i++) 
        {
            fill(dist[i].begin(), dist[i].end(), INT_MAX);
        }

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
        pq.push({ arr[0][0], {0, 0} });
        dist[0][0] = arr[0][0];

        while (!pq.empty())
        {
            int y = pq.top().second.first;
            int x = pq.top().second.second;
            int curDist = pq.top().first;
            pq.pop();

            for (int i = 0; i < 4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

                int nextDist = curDist + arr[ny][nx];
                if (nextDist < dist[ny][nx])
                {
                    dist[ny][nx] = nextDist;
                    pq.push({ nextDist, { ny, nx } });
                }
            }
        }

        cout << "Problem " << index++ << ": " << dist[N - 1][N - 1] << '\n';
    }


    return 0;
}

회고

다익스트라 알고리즘을 최근에 많이 사용했더니 관련 문제가 잘 풀린다. 이 문제는 다익스트라 말고 그냥 일방적인 BFS로도 풀 수 있다

BFS는 완전탐색에 가까운 시간 복잡도가 걸려 사실 최단경로를 찾는 다익스트라를 쓰는 것이 효율적일 것 같다