진격의 거인 문제

개요

친구랑 진격의 거인 더 라스트 어택을 보고 감격을 받아서 코딩테스트 문제를 직접 만들었다. (안본 사람은 꼭 보았으면 좋겠다.)

문제

애렌의 땅울림 최단거리 에렌은 (0, 0) 위치의 파라디 섬에서 출발하여, 목표 지점 (y, x)까지 도달하여 땅울림을 실행하려 한다. 에렌은 1로 표시된 땅에서만 땅울림을 이어갈 수 있 고, 0으로 표시된 곳은 갈 수 없는 곳이다. 또한, 진격의 거인의 힘으로 인해 한 번 밟은 땅은 다 시는 되돌아갈 수 없다. 에렌이 목표 지점까지 이동할 수 있는 최단 거리를 구해보자. 만약 도달할 수 없다면 -1을 출력하자. (최단 거리 문제가 나오면 자동반사로 BFS 를 먼저 떠올리게 된다.)

입력

N, M ≤ 1,000

출력

코드

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

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
const int max_n = 100;
int n, m;
int y, x;
int a[max_n][max_n], visited[max_n][max_n];

void FASTIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    FASTIO();
    cin >> n >> m;
    cin >> y >> x;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    queue<pair<int, int>> q;
    if (a[0][0] == 0) {
        cout << -1 << '\n';
        return 0;
    }

    q.push({0, 0});
    visited[0][0] = 1;

    while (!q.empty()) {
        auto [y, x] = q.front();
        q.pop();

        if (y == y && x == x) {
            cout << visited[y][x] - 1 << '\n';
            return 0;
        }

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

            if (ny < 0 || ny >= n || nx < 0 || nx >= m)
                continue;
            if (a[ny][nx] == 0 || visited[ny][nx] != 0)
                continue;

            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }

    cout << -1 << '\n'; // 도달 불가
    return 0;
}

접근

이 문제는 2차원 맵 위에서 (0, 0) 지점에서 출발하여 (y, x) 지점까지 갈 수 있는지, 그리고 도달할 수 있다면 그 최단 거리가 얼마인지 묻고 있다. 이동할 수 있는 곳은 값이 1인 지점뿐이고, 한 번 밟은 땅은 다시는 밟을 수 없으므로 방문한 곳은 다시 가지 않도록 처리해야 한다. 이러한 조건은 전형적인 너비 우선 탐색(BFS) 문제라는 것을 암시한다(자동 반사처럼 나와야 한다.) BFS는 시작 지점에서부터 모든 방향으로 거리를 1씩 늘려가며 탐색하기 때문에, 어떤 지점에 가장 먼저 도달했을 때 그 거리가 곧 최단 거리라는 특징을 가진다. 따라서 (0, 0)부터 시작해서 갈 수 있는 지점을 큐에 넣고, 방문할 때마다 현재 거리 +1 값을 기록하면서 진행하면 된다. 이를 위해 방문 여부와 동시에 거리를 저장할 visited 배열을 활용할 수 있다. 만약 어떤 지점이 이미 방문된 상태라면, 다시 큐에 넣지 않고 건너뛰는 방식으로 처리하면 된다. 탐색을 진행하다가 현재 위치가 우리가 찾고자 하는 목표 지점 (y, x)에 도달했을 경우, 그 지점의 visited 값 -1 시작점에서 1부터 시작했으므로)을 출력하고 탐색을 종료한다. 만약 BFS가 종료될 때까지도 목표 지점에 도달하지 못했다면, 이는 갈 수 없는 경우이므로 -1을 출력하면 된다. 또한 문제에서 자료구조를 큐를 사용한 이유는 BFS는 시작 지점에서부터 인접한 모든 지점을 먼저 방문하고, 그 다음으로 더 먼 지점들을 방문해 나가는 방식이기 때문이다. 인접노드를 떠올리면 쉽다.

Reference

나의 뇌