[C++] BOJ 2178번: 미로 탐색

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다.

 

문제의 난이도는 실버 1로, BFS(너비 우선 탐색)를 활용해 푸는 것을 권장받은 문제이다.

문제 링크

https://www.acmicpc.net/problem/2178

문제 분석

  주어진 미로에 대해 (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성해야 한다. 이 때, 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

자료 구조

1. 큐 (Priority Queue)

 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO형 자료구조이다. BFS를 구현할 때에는 큐를 사용하여 구현한다.

 

2. BFS 알고리즘

 BFS는 그래프 탐색 알고리즘 중 하나이다. DFS와 달리 함수를 통해 재귀적으로 구현할 수 없다. 이는 DFS가 자료구조 스택을 통해 구현되는 것과 달리 BFS는 자료구조 큐를 사용하여 구현되기 때문이다.

 

문제 풀이

 이 문제의 핵심 키워드는 '서로 인접한 칸으로만 이동 가능', '이동할 때 지나야 하는 최소의 칸 수'이다.

 문제를 풀 때 주의해야 할 점으로 미로 입력이 주어질 때 각각의 수들이 붙어서 입력으로 주어진다는 점이 있다. 따라서 미로에 대한 입력을 받을 때에

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        cin >> map[i][j];
    }
}

위와 같이 하나 하나 입력받는 게 아닌

for (int i = 0; i < N; i++)
{
    string input;
    cin >> input;
    for (int j = 0; j < M; j++)
    {
        map[i][j] = input[j];
    }
}

위와 같은 형태로 코드를 작성해야 한다.

전체 코드

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

using namespace std;

queue<pair<int, int>> q;
int map[101][101];
int values[101][101];

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

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        string input;
        cin >> input;
        for (int j = 0; j < M; j++)
        {
            map[i][j] = input[j] - '0';
        }
    }

    values[0][0] = 1;

    q.push({0, 0});

    while (!q.empty())
    {
        pair<int, int> cpos = q.front();
        q.pop();
        int cy = cpos.first;
        int cx = cpos.second;

        for (int i = 0; i < 4; i++)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N)
                continue;
            if (values[ny][nx] != 0 || map[ny][nx] == 0)
                continue;
            values[ny][nx] = values[cy][cx] + 1;
            q.push({ny, nx});
        }
    }

    cout << values[N - 1][M - 1] << '\n';

    return 0;
}