BOJ 14923 · 미로 탈출

알고리즘 분류 : BFS  

벽을 하나 뚫고 미로를 탈출하는 것을 구현해야 한다. BOJ 2206번 '벽 부수고 이동하기'와 유사한 문제이다.

• 입력으로 주어진 출발점(HX, HY)부터 탈출 위치(EX, EY)까지 BFS 탐색을 통해 이동한다.
• 이동 거리 저장과 방문 여부를 체크할 배열 dist를 3차원 배열로 선언한다.
• dist의 인덱스는 [X 좌표] [Y좌표] [벽 부순 횟수] 이다.
• 벽(1)을 만나면, 벽을 아직 부수지 않은 경우 벽을 부수고 이동한다. 벽을 이미 부순 경우 이동하지 않는다.
• 빈칸(0)은 그대로 이동한다.

---

C++ 소스코드

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

struct maze {
    int x, y, z;
};

int n, m, hx, hy, ex, ey;
int a[1000][1000];
int dist[1000][1000][2];
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};

void bfs() {
    queue<maze> q;
    q.push({hx-1, hy-1, 0});
    dist[hx-1][hy-1][0] = 0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, z = q.front().z; q.pop();
        if (x == ex-1 && y == ey-1) {
            printf("%d\n", dist[x][y][z]);
            return;
        }
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i], nz = z;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (a[nx][ny]) {
                if (nz) continue;
                else nz = 1;
            }
            if (dist[nx][ny][nz] == -1) {
                q.push({nx, ny, nz});
                dist[nx][ny][nz] = dist[x][y][z]+1;
            }
        }
    }
    printf("-1\n");
}

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

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int, input().split())
hx, hy = map(int, input().split())
ex, ey = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
dist = [[[-1, -1] for _ in range(m)] for _ in range(n)]
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def bfs():
    q = deque()
    q.append((hx-1, hy-1, 0))
    dist[hx-1][hy-1][0] = 0
    while q:
        x, y, z = q.popleft()
        if x == ex-1 and y == ey-1:
            return dist[x][y][z]
        for i in range(4):
            nx, ny, nz = x+dx[i], y+dy[i], z
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if a[nx][ny]:
                if nz:
                    continue
                else:
                    nz = 1
            if dist[nx][ny][nz] == -1:
                dist[nx][ny][nz] = dist[x][y][z]+1
                q.append((nx, ny, nz))
    return -1

print(bfs())

---

참고

• 백준 온라인 저지 : BOJ 14923
• 벽 부수고 이동하기