C++ 코딩테스트 강좌, 미로 탐색하기

문제 설명

주어진 미로를 탐색하여 출구까지 가는 경로를 찾는 문제입니다. 미로는 2차원 배열로 주어지며,
0은 이동할 수 있는 경로, 1은 벽을 의미합니다. 시작점은 (0, 0)이고, 출구는 (n-1, m-1)입니다.
미로의 크기는 n x m이며, 미로를 탐색하는 알고리즘을 구현하시오.

입력 형식

첫째 줄에 미로의 크기 n과 m이 주어집니다. (1 ≤ n, m ≤ 100)
다음 n개의 줄에는 0과 1로 이루어진 미로의 정보가 주어집니다.

출력 형식

출구까지 도달할 수 있다면 그 경로의 길이를 출력하고, 불가능하다면 -1을 출력합니다.

예제 입력

예제 출력

문제 해결 접근 방법

이 문제는 BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 활용하여 미로를 탐색할 수 있습니다.
BFS는 가장 먼저 발견된 경로가 최단 경로이므로, 그리드 탐색 시 BFS를 추천합니다.

BFS를 사용할 경우, 큐를 활용하여 현재 위치에서 이동 가능한 노드를 탐색하고,
방문 여부를 체크한 후, 새로운 위치를 큐에 추가합니다.
이러한 방법으로 출구에 도달하는 가장 짧은 경로를 찾아낼 수 있습니다.

C++ 코드 구현

아래는 미로 탐색 문제를 해결하기 위한 C++ 코드입니다.


#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

// 이동 방향: 상, 하, 좌, 우
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int bfs(const vector>& maze, int n, int m) {
    queue> q; // 큐 선언
    q.push({0, 0}); // 시작 위치 (0, 0)
    
    vector> distance(n, vector(m, -1)); // 거리 배열
    distance[0][0] = 1; // 시작점 거리 1로 초기화

    while (!q.empty()) {
        auto current = q.front(); q.pop();
        int x = current.first;
        int y = current.second;

        // 목표 지점에 도달한 경우
        if (x == n - 1 && y == m - 1) {
            return distance[x][y]; // 경로 길이 반환
        }

        // 인접 노드 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위 체크 및 이동 가능한지 확인
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                maze[nx][ny] == 0 && distance[nx][ny] == -1) {
                q.push({nx, ny}); // 큐에 추가
                distance[nx][ny] = distance[x][y] + 1; // 거리 업데이트
            }
        }
    }
    return -1; // 출구에 도달하지 못한 경우
}

int main() {
    int n, m;
    cin >> n >> m; // 미로 크기 입력
    vector> maze(n, vector(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j]; // 미로 입력
        }
    }

    cout << bfs(maze, n, m) << endl; // 결과 출력
    return 0;
}

코드 설명

위 코드는 2차원 벡터를 사용하여 미로를 표현하고, BFS를 통해 출구까지의 거리를 계산합니다.
주요 구성 요소로는:

큐(Queue): 현재 탐색 중인 노드를 저장하여 다음 이동할 노드를 결정하는 데 사용됩니다.
거리 배열(Distance Array): 각 노드까지의 거리를 기록하여 이미 방문한 노드를 다시 방문하지 않도록 합니다.
이동 방향 배열: 상, 하, 좌, 우 방향으로 이동할 수 있도록 dx와 dy 배열을 설정했습니다.

프로그램이 수행될 때, 시작점에서 BFS를 수행하며 모든 인접 노드를 탐색하게 됩니다.
출구에 도달하면 해당 지점까지의 길이를 반환하며, 도달하지 못한 경우 -1을 반환합니다.

시간 복잡도

시간 복잡도는 O(n * m)입니다. 모든 노드를 한 번씩 방문하기 때문입니다.
공간 복잡도 또한 역시 O(n * m)으로, 거리 배열과 큐를 사용하기 때문입니다.

마치며

이번 강좌에서는 C++를 이용한 미로 탐색 문제를 해결하기 위해 BFS 알고리즘을 구현해보았습니다.
알고리즘의 기본 개념을 이해하고, 실습을 통해 실제 코드를 작성하는 데에 도움을 줄 수 있기를 바랍니다.
그러므로, 다양한 형태의 미로 탐색 문제를 통해 경험치를 쌓아가길 추천합니다.

자신의 코드를 더욱 개선하기 위해 다양한 테스트 케이스를 만들어보는 것도 좋은 학습 방법입니다.