C++로 미로 밖으로 탈출 가능한지 판별하는 방법

이 문제에서는 n개의 정수로 이루어진 미로가 주어집니다. 각 정수는 이동해야 할 칸 수를 의미하고, '>' 또는 '<' 기호는 이동 방향을 나타냅니다. 시작 지점은 인덱스 0이며, 이곳에서 출발했을 때 미로 밖으로 빠져나올 수 있는지 판별하는 것이 목표입니다.

문제 이해를 위한 예시

입력 −

4
2 1 1 4
> < > >

출력 −

YES

설명 − 시작 위치에서 먼저 2칸 앞으로 이동하고, 다음으로 1칸, 마지막으로 4칸 앞으로 이동하면 미로 밖으로 탈출하게 됩니다.

해결 접근 방식

미로 탈출이 가능하려면 이동 과정에서 현재 위치가 0 미만이 되거나 n 이상이 되어야 합니다. 따라서 인덱스 0에서 출발해 각 칸에 적힌 방향과 거리만큼 위치를 옮겨 가며, 탈출 조건(미로 범위를 벗어남)에 도달하는지 확인하면 됩니다.

여기서 반드시 고려해야 할 또 다른 상황은 무한 루프입니다. 이미 방문했던 칸을 다시 밟게 되면 같은 경로를 영원히 반복하며 미로를 빠져나올 수 없게 됩니다. 이를 감지하기 위해 모든 방문 위치를 표시(mark)해 두었다가, 재방문이 발생하는 순간 탈출이 불가능하다고 판단합니다.

구현 예제

위 접근 방식을 구현한 프로그램은 다음과 같습니다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void isMazeSolvable(int a[], int n, string s) {
    vector<int> mark(n, 0);   // 방문 여부 표시 배열
    int start = 0;
    bool possible = true;

    // 현재 위치가 미로 범위(0 ~ n-1) 안에 있는 동안 반복
    while (start >= 0 && start < n) {
        if (mark[start] == 1) {   // 이미 방문한 칸 → 무한 루프 발생
            possible = false;
            break;
        }
        mark[start] = 1;

        if (s[start] == '<')
            start -= a[start];   // 왼쪽으로 이동
        else
            start += a[start];   // 오른쪽으로 이동
    }

    if (!possible)
        cout << \"미로 안에 영원히 갇히게 됩니다\";
    else
        cout << \"미로 밖으로 탈출할 수 있습니다\";
}

int main() {
    int n = 3;
    string s = \">><\";
    int a[] = {1, 2, 4};
    isMazeSolvable(a, n, s);
    return 0;
}

출력 결과

미로 밖으로 탈출할 수 있습니다

복잡도 분석

시간 복잡도: O(n) — 각 칸은 최대 한 번씩만 방문됩니다.
공간 복잡도: O(n) — 방문 여부를 저장하는 배열이 필요합니다.

정리

이 문제의 핵심은 방문 표시 배열입니다. 같은 칸을 두 번 이상 밟는 순간 무한 루프임을 즉시 알 수 있어, 불필요한 반복 없이 빠르고 정확하게 답을 도출할 수 있습니다. 시뮬레이션 기반 문제에서 무한 루프 가능성이 있다면 반드시 방문 처리를 함께 설계하는 습관이 중요합니다.