BOJ 23563 - 벽 타기 링크
(2023.08.10 기준 G3)

문제

높이가 H, 너비가 W인 맵이 격자판 모양으로 주어진다.
각 칸은 벽 또는 빈칸인데, 벽으로는 이동하지 못하며 상하좌우 인접한 칸으로 이동할 수 있으며, 1칸 당 1초가 걸린다. 하지만, 벽과 인접한 칸에서 벽과 인접한 칸으로 이동하는 것은 0초가 걸린다.
시작점에서 끝점까지 이동하는 데 걸리는 최소 시간 출력

알고리즘

0-1 BFS

풀이

0초 또는 1초가 걸린다. 즉, 가중치는 0 또는 1인 그래프에서의 최단 경로를 구하는 문제이므로 0-1 BFS를 사용하면 된다.

먼저, 각 칸의 정보를 전처리하자. 벽과 인접한 빈칸은 0, 벽과 인접하지 않은 빈칸은 1, 벽은 2를 할당하면 된다.

그리고 시작점에서 0-1 BFS를 시작하면 되고, 현재 칸과 다음 칸이 둘 다 0이어야 가중치가 0이 됨을 꼭 잊지 말자.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int inf = INT_MAX;

pii dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int H, W; cin >> H >> W;
    string matrix[H]; for (int i = 0; i < H; i++) cin >> matrix[i];

    int si, sj, ei, ej, w[H][W]; // 0 : 벽에 인접한 빈칸, 1 : 벽에 인접하지 않은 빈칸, 2 : 벽
    fill(&w[0][0], &w[H - 1][W], 1);
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++){
        if (matrix[i][j] == '#'){ // 벽
            w[i][j] = 2;
            continue;
        }
        if (matrix[i][j] == 'S') // 시작점
            si = i, sj = j;
        else if (matrix[i][j] == 'E') // 끝점
            ei = i, ej = j;
        for (auto [di, dj]: dir) // 벽에 인접한 지 확인
            if (0 <= i + di && i + di < H && 0 <= j + dj && j + dj < W && matrix[i + di][j + dj] == '#'){
                w[i][j] = 0;
                break;
            }
    }

    // 시작점부터 0-1 BFS 시작
    deque<tiii> dq; dq.push_back({0, si, sj}); // 거리, 행 번호, 열 번호
    int distance[H][W]; fill(&distance[0][0], &distance[H - 1][W], inf);
    distance[si][sj] = 0;

    while (!dq.empty()){
        auto [d, i, j] = dq.front(); dq.pop_front();
        if (distance[i][j] < d) continue;
        for (auto [di, dj]: dir)
            if (0 <= i + di && i + di < H && 0 <= j + dj && j + dj < W){
                if (!w[i][j] && !w[i + di][j + dj]){ // 벽에 인접한 빈칸 -> 벽에 인접한 빈칸 (가중치 0)
                    if (distance[i + di][j + dj] > d){
                        distance[i + di][j + dj] = d;
                        dq.push_front({d, i + di, j + dj}); // deque 앞에 넣기
                    }
                }
                else if (w[i + di][j + dj] != 2){ // 벽으로 이동하는 경우를 제외한 나머지 (가중치 1)
                    if (distance[i + di][j + dj] > d + 1){
                        distance[i + di][j + dj] = d + 1;
                        dq.push_back({d + 1, i + di, j + dj}); // deque 뒤에 넣기
                    }
                }
            }
    }

    cout << distance[ei][ej];
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from collections import deque
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우

H, W = map(int, input().split())
matrix = [input().strip() for _ in range(H)]

w = [[1] * W for _ in range(H)] # 0 : 벽에 인접한 빈칸, 1 : 벽에 인접하지 않은 빈칸, 2 : 벽
for i in range(H):
    for j in range(W):
        if matrix[i][j] == '#': # 벽
            w[i][j] = 2
            continue
        if matrix[i][j] == 'S': # 시작점
            si = i; sj = j
        elif matrix[i][j] == 'E': # 끝점
            ei = i; ej = j
        for di, dj in dir: # 벽에 인접한 지 확인
            if 0 <= i + di < H and 0 <= j + dj < W and matrix[i + di][j + dj] == '#':
                w[i][j] = 0
                break

# 시작점부터 0-1 BFS 시작
dq = deque([(0, si, sj)]) # 거리, 행 번호, 열 번호
distance = [[inf] * W for _ in range(H)]
distance[si][sj] = 0

while dq:
    d, i, j = dq.popleft()
    if distance[i][j] < d:
        continue
    for di, dj in dir:
        if 0 <= i + di < H and 0 <= j + dj < W:
            if not w[i][j] and not w[i + di][j + dj]: # 벽에 인접한 빈칸 -> 벽에 인접한 빈칸 (가중치 0)
                if distance[i + di][j + dj] > d:
                    distance[i + di][j + dj] = d
                    dq.appendleft((d, i + di, j + dj)) # deque 앞에 넣기
            elif w[i + di][j + dj] != 2: # 벽으로 이동하는 경우를 제외한 나머지 (가중치 1)
                if distance[i + di][j + dj] > d + 1:
                    distance[i + di][j + dj] = d + 1
                    dq.append((d + 1, i + di, j + dj)) # deque 뒤에 넣기

print(distance[ei][ej])