BOJ 6189 · Munching

알고리즘 분류 : BFS  

전형적인 미로 탈출 문제이다. BFS를 통해 최단 이동 거리를 구하면 된다.

• 'B'부터 출발해서 'C'에 도착하면 된다.
• 장애물('*')은 지날 수 없다.
• 인접 4방향으로 BFS 탐색을 진행하면 된다.

---

C++ 소스코드

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

struct grid {
    int x, y;
};

int r, c, sx, sy;
char a[101][101];
int dist[100][100];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    queue<grid> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        if (a[x][y] == 'C') {
            printf("%d\n", dist[x][y]);
            return;
        }
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (dist[nx][ny] == -1 && a[nx][ny] != '*') {
                q.push({nx, ny});
                dist[nx][ny] = dist[x][y]+1;
            }
        }
    }
}

int main() {
    scanf("%d %d", &r, &c);
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            scanf(" %1c", &a[i][j]);
            dist[i][j] = -1;
            if (a[i][j] == 'B') sx = i, sy = j;
        }
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

from collections import deque

def bfs(i, j):
    q = deque()
    q.append((i, j))
    dist[i][j] = 0
    while q:
        x, y = q.popleft()
        if a[x][y] == 'C':
            print(dist[x][y])
            return
        for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            if dist[nx][ny] == -1 and a[nx][ny] != '*':
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y]+1

r, c = map(int, input().split())
a = [list(input().strip()) for _ in range(r)]
dist = [[-1]*c for _ in range(r)]
for i in range(r):
    for j in range(c):
        if a[i][j] == 'B':
            bfs(i, j)

---

참고

• 백준 온라인 저지 : BOJ 6189