BOJ 2665 · 미로만들기

알고리즘 분류 : BFS  

미로를 이동하면서 검은 방을 흰 방으로 만드는 최소 횟수를 구해야 하는 문제다. 덱(Deque)과 BFS를 이용하여 해결할 수 있다. 이 문제는 BOJ 1261 '알고스팟' 문제와 유사하다.

• 흰 방을 이동할 때는 덱의 뒤에 넣고, 이동 거리는 이전과 같게 한다.
• 검은 방을 이동할 때는 덱의 앞에 넣고, 이동 거리를 +1 업데이트한다.
• 덱에서 이동 좌표를 꺼낼 때, 덱의 뒤에서부터 꺼낸다.

---

C++ 소스코드

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

struct maze {
    int x, y;
};

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

void bfs() {
    deque<maze> q;
    q.push_back({0, 0});
    dist[0][0] = 0;
    while (!q.empty()) {
        int x = q.back().x, y = q.back().y; q.pop_back();
        if (x == n-1 && y == n-1) {
            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 >= n || ny < 0 || ny >= n) continue;
            if (dist[nx][ny] >= 0) continue;
            if (a[nx][ny]) {
                dist[nx][ny] = dist[x][y];
                q.push_back({nx, ny});
            } else {
                dist[nx][ny] = dist[x][y]+1;
                q.push_front({nx, ny});
            }
        }
    }
}

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

---

Python 3 소스코드

from collections import deque

n = int(input())
a = [list(input().strip()) for _ in range(n)]
dist = [[-1]*n for _ in range(n)]

def bfs():
    q = deque()
    q.append((0, 0))
    dist[0][0] = 0
    while q:
        x, y = q.pop()
        if x == n-1 and y == n-1:
            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 >= n or ny < 0 or ny >= n:
                continue
            if dist[nx][ny] == -1:
                if a[nx][ny] == '1':
                    dist[nx][ny] = dist[x][y]
                    q.append((nx, ny))
                else:
                    dist[nx][ny] = dist[x][y]+1
                    q.appendleft((nx, ny))

bfs()

---

참고

• 백준 온라인 저지 : BOJ 2665
• 알고스팟