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

문제

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

풀이

[백준][C++] 1261: 알고스팟

너비 우선 탐색 문제로, 위의 문제와 풀이가 동일하다.

 

• 하나 주의해야 할 점은, 시작 지점의 거리가 0이 아니고, 시작 지점의 도둑 루피의 크기이다. 
• 거리를 나타내는 배열이 2차원 배열임을 주목하자.

코드

#include <iostream>

using namespace std;

int N;
int room[125][125];
int dist[125][125];

int move_x[4] = { -1, 0, 1, 0 };
int move_y[4] = { 0, 1, 0, -1 };

void solution(int start_x, int start_y)
{
    // 시작 위치의 거리는 0이 아니라 시작 위치의 도둑 루피의 크기이다.
    dist[start_x][start_y] = room[start_x][start_y];

    queue<pair<int, int>> q;
    q.push(make_pair(start_x, start_y));

    while (!q.empty())
    {
        int current_x = q.front().first;
        int current_y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            // 현재 칸의 상하좌우를 탐색
            int next_x = current_x + move_x[i];
            int next_y = current_y + move_y[i];
            if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N)
            {
                continue;
            }

            // 다음 칸의 거리를 갱신할 수 있다면 갱신하고, 큐에 넣는다.
            int next_dist = dist[current_x][current_y] + room[next_x][next_y];
            if (next_dist < dist[next_x][next_y])
            {
                dist[next_x][next_y] = next_dist;
                q.push(make_pair(next_x, next_y));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int count = 0;
    while (cin >> N)
    {
        if (N == 0)
        {
            break;
        }

        count++;

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

        solution(0, 0);

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

    return 0;
}