BOJ 2178 · 미로 탐색

알고리즘 분류 : BFS  

BFS를 통해 최단 거리를 구하는 문제이다.

• 먼저 N x M 크기의 배열에 값을 입력받는다.
• 1은 이동 가능하고, 0은 이동 불가능하므로, BFS 탐색을 하면서 값이 0인 곳으로 이동하지 않도록 구현한다.
• 현재 좌표가 N, M이면 탐색을 중지해도 되므로, break를 건다.
• 출발 좌표가 (0,0)이면 (N-1, M-1)이 도착이고, (1, 1)에서 출발했으면 (N, M)이 도착이다.
• 이동하면서 좌표가 배열 범위를 벗어나지 않도록 체크한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct maze {
    int x, y;
};

int n, m;
int a[101][101];
int dist[101][101];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    queue<maze> q;
    q.push({1, 1});
    dist[1][1] = 1;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        if (x == n && y == m) { // Arrived at (N, M)
            printf("%d\n", dist[n][m]);
            break;
        }
        for (int i=0; i<4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            // Already visited, if dist[nx][ny] > 0.
            // Blocked, if a[nx][ny] is 0.
            if (dist[nx][ny] || !a[nx][ny]) continue;
            dist[nx][ny] = dist[x][y] + 1;  // Distance count
            q.push({nx, ny});
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

import sys

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, sys.stdin.readline().split())
dist = [[0]*m for _ in range(n)]
a = []
for _ in range(n):
    a.append(sys.stdin.readline())

def bfs():
    q = [(0, 0)]
    dist[0][0] = 1
    while q:
        x, y = q.pop(0)
        if x == n-1 and y == m-1:
            print(dist[x][y])
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if dist[nx][ny] > 0 or a[nx][ny] == '0':
                continue
            dist[nx][ny] = dist[x][y] + 1
            q.append((nx, ny))

bfs()

---

참고

• 백준 온라인 저지 : BOJ 2178