문제 푼 날짜 : 2021-07-07

문제

문제 링크 : https://www.acmicpc.net/problem/4485

접근 및 풀이

이전에 풀어본 다익스트라 문제와 달리 배열을 통해 경로를 탐색하며 다익스트라 알고리즘을 적용시켜야 했다. 구현하는데 있어서 크게 다른 점은 없고, BFS를 이용한 문제를 풀때처럼 상하좌우로 배열을 움직일 때 조건을 체크하는 부분이 추가되었다.
최단경로를 저장하는 배열 또한 2차원으로 지정해 주었고, 방문표시를 위한 배열도 선언해주었다.

코드

// 백준 4485번 : 녹색 옷 입은 애가 젤다지?
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define INF 987654321

int N;
int map[126][126];
int visited[126][126];
int dist[126][126];

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

void dijkstra() {
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push(make_pair(0, make_pair(0, 0)));
    visited[0][0] = true;

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

        for (int i = 0; i < 4; i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            int nextCost = cost + map[nextY][nextX];

            if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N) {
                continue;
            }
            if (visited[nextY][nextX] == false && dist[nextY][nextX] > nextCost) {
                dist[nextY][nextX] = nextCost;
                visited[nextY][nextX] = true;
                pq.push(make_pair(-nextCost, make_pair(nextY, nextX)));
            }
        }
    }
}

int main() {
    int num = 1;
    while (true) {
        cin >> N;

        if (N == 0) {
            break;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
                dist[i][j] = INF;
            }
        }
        memset(visited, false, sizeof(visited));
        dijkstra();

        cout << "Problem " << num++ << ": " << map[0][0] + dist[N - 1][N - 1] << '\n';
    }
    return 0;
}

피드백

문제에서 배열로 주어지니 처음엔 당황하여 어떻게 해결해야할지 헤매었다.
기본적인 문제말고 좀 더 다양한 유형과 심화문제를 풀어봐야겠다.