https://www.acmicpc.net/problem/14923

일반적인 BFS 문제였다. [벽 부수고 이동하기] 에 대해 제대로 이해했다면 충분히 풀 수 있다.

문제

문제에서 추출해야 할 조건은 다음과 같다.

• 출발점에서 도착점까지 이동하는 최단 거리(시간)을 출력한다.
• 딱 1번 벽을 깨고 이동할 수 있으며, 벽을 부수는 데 추가적인 시간이 걸리진 않는다.

입출력

0과 1로 된 미로를 탈출한다. 0은 길, 1은 벽이다.
탈출할 수 없다면 -1을 출력한다는 추가적인 조건이 존재한다.

입력 로직은 대부분의 BFS와 동일하기에 생략한다.

중요한 것은 "어떻게 벽을 부수거나 부수지 않았는지를 표현할 것인가?" 이다.
나는 visited 배열을 3차원으로 확장하였다. (다른 방법도 충분히 존재한다.)
visited[1000][1000][2]를 선언하여, 마지막 인덱스는 현재까지의 위치에 도달하는 동안 벽을 부수지 않았는지(1) 혹은 이미 부수었는지(0)를 표현하도록 약속하였다.
queue에 출발점과 벽 부수기 찬스를 나타내는 1을 넣고 방문처리해주었다.

큐에서 데이터를 꺼냈을 때 크게 두 가지로 나눌 수 있다.
1. 아직 방문하지 않았으며, 갈 수 있는 길(즉 map이 0)
2. 벽(map이 1)이면서 벽을 부술 수 있을 때(큐의 second가 1)
-> 이 경우 방문 여부를 따지면 안 된다. 한번이라도 어떤 노드에서 부서진 벽일 경우 전체 노드가 이쪽 시도를 포기한다.

이렇게 조건문을 완성했다면 끝이다.
1부터 visited가 시작되었으므로 도착점 결과에서 1을 빼주어야 한다.

소스 코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int visited[1000][1000][2];
int n, m, sx, sy, ex, ey;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int map[1000][1000];

void BFS(int sx, int sy){
    queue<pair<pair<int,int>, int> > q;
    q.push(make_pair(make_pair(sx-1, sy-1), 1));
    visited[sx-1][sy-1][1] = 1; // 초기값 설정

    while(!q.empty()){
        int r = q.front().first.first;
        int c = q.front().first.second;
        int breakflag = q.front().second; // 벽 부숨 여부
        q.pop();

        if(r == ex-1 && c == ey-1){ // 도착
            cout << visited[r][c][breakflag]-1 << '\n';
            return;
        }

        for(int i=0; i<4; i++){
            int nr = r + dx[i];
            int nc = c + dy[i];

            if(nr >= 0 && nr < n && nc >= 0 && nc < m){
                if(map[nr][nc] == 0 && visited[nr][nc][breakflag] == 0){ // 방문하지 않은 '길'
                    q.push(make_pair(make_pair(nr, nc), breakflag));          
                    visited[nr][nc][breakflag] = visited[r][c][breakflag] + 1;
                } else if(map[nr][nc] == 1 && breakflag == 1){ // 현재 부술 수 있는(breakflag = 1) '벽'
                    q.push(make_pair(make_pair(nr, nc), breakflag-1));
                    visited[nr][nc][breakflag-1] = visited[r][c][breakflag] + 1;
                }
            }
        }
    }
    cout << -1; // 탈출 실패
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    cin >> sx >> sy;
    cin >> ex >> ey;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    } // 입력

    memset(visited, 0, sizeof(visited)); // 초기화
    BFS(sx, sy);
    return 0;
}

교훈

• BFS는 정확도와 속도 모두가 생명이다. BFS임을 확인했다면 queue를 활용하면서 여러 범위 조건이나 방문 조건 등을 빠르고 정확하게 체크하자.