문제 링크

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

문제 설명

N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

문제 분석

문제는 최단 경로를 구하는 것이기 때문에 너비 우선 탐색(BFS)을 사용을 해야겠다고 생각했다. BFS는 각 단계에서 모든 인접한 칸을 한 번씩 탐색하고, 가장 먼저 목표 지점에 도달한 경로가 최단 경로가 되는 특징이 있다. 그리고 마침 가중치도 같으니 BFS가 적합하다. 만약 가중치의 값이 다 달랐다면 벨만포드, 다익스트라를 고려했을 거 같다.

코드

#include<bits/stdc++.h>
using namespace std;
const int max_n = 104;
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int n,m, a[max_n][max_n], visited[max_n][max_n], y,x;
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%1d", &a[i][j]);
        }
    }
    queue<pair<int,int>> q;
    visited[0][0] = 1;
    q.push({0, 0});
    while(q.size()){
        tie(y,x) = q.front();
        q.pop();
        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 || a[ny][nx] == 0){
                continue;
            }
            if(visited[ny][nx]){
                continue;
            }
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny,nx});
        }
    }
    printf("%d", visited[n - 1][m - 1]);
    return 0;
}

이 코드는 너비 우선 탐색(BFS)을 사용하여 2차원 배열 형태의 미로에서 시작점 0,0 에서 끝점 n-1, m-1 까지의 최단 경로를 찾는 프로그램이다. 미로의 각 칸은 1로 표시된 길과 0으로 표시된 벽으로 이루어져 있으며, BFS를 통해 최소 이동 거리를 계산한다. 우선, n과 m으로 미로의 크기를 입력받고, 2차원 배열 a에 미로의 정보를 저장한다. 각 칸은 한 자리 숫자(%1d)로 입력받아 길(1)과 벽(0)을 나타낸다. 이후 탐색을 위해 큐를 생성하고, 시작점인 {0,0}을 큐에 넣은 후 방문 배열인 visited 에 방문 여부와 해당 위치까지의 이동 거리를 기록한다. BFS 알고리즘은 큐에서 하나씩 좌표를 꺼내 네 방향(상, 우, 하, 좌)으로 이동 가능한지를 확인한다. 이때, 배열 범위를 벗어나거나 벽이 있는 경우, 또는 이미 방문한 경우는 건너뛴다. 방문하지 않은 칸이면 해당 칸의 이동 거리를 이전 칸의 이동 거리에서 1을 더한 값으로 기록하고 큐에 삽입한다. 모든 탐색이 끝난 후 목표 지점인 n-1, m-1에 기록된 이동 거리를 출력하여 최단 경로의 길이를 구한다.

Reference

나의 뇌