[BOJ, C++]#2206_벽 부수고 이동하기, 미로 찾기 유형, 최단 경로, BFS

#1. 문제

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

 

---

 

#2. 풀이

 

1. 최단 경로

[알고리즘]#2_길 찾기 알고리즘

최단 경로 알고리즘은 그래프 자료구조에서 출발점과 도착점 사이의 경로를 찾는 알고리즘입니다. 특히, 무 가중치 혹은 동일한 가중치를 갖는 그래프 자료구조에서 단일-쌍 최단 경로를 구하기 위해 BFS가 활용됩니다. 

 

2. 각 칸의 최단 경로 값을 두 가지 경우로 나누자!

1. 먼저, 2차원 벡터 컨테이너를 통해 그래프를 구성합니다.
2. 그리고, 3차원 벡터 컨테이너를 통해 각 칸에 대하여 두 가지 방문 여부(현재 정점에 벽을 이미 부수고 도착했는가? 현재 정점에 벽을 부수지 않고 도착했는가?)를 확인합니다.
3. 기존의 미로 찾기 유형을 풀이했던 방법대로 BFS를 수행합니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/2206
*   @문제: NxM 크기의 맵에서 (1,1) 위치에서 (N, M)위치까지 도착하는 최단 경로 구하기
*   @설명
        1. 미로 찾기 유형 + 벽 부수기
        2. 3차원 배열을 통해 각 칸의 방문여부 체크
        - [ny][nx][0] 과 [ny][nx][1]로 구분합니다.
        - 어떤 탐색 경로에서 [ny][nx]를 '벽'을 부순 상태로 방문했는가, 혹은 '벽'을 부수지 않은 상태에서 방문했는가 구분합니다.
        - 1번 탐색 경로에서 이미 벽을 한 번 부수고 [ny][nx]를 방문했다면, 2번 탐색 경로는 이미 벽을 한 번 부수고 [ny][nx]를 방문할 수 없도록 합니다.
        - 1번 탐색 경로에서 이미 벽을 한 번 부수고 [ny][nx]를 방문했다면, 2번 탐색 경로는 벽을 한 번도 부수지 않은 상태에서 [ny][nx]를 다시 방문할 수 있습니다.
        * 같은 정점이라도 벽을 부수고 방문하는 경로와 벽을 부수지 않고 방문하는 경로는 서로 다른 최단 경로 값을 가질 수 있기때문에, 정점의 방문 여부를 두 가지 상태로 구분해줍니다.
*/

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX 1001

int N, M;
vector<vector<int>> board(MAX, vector<int>(MAX));
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};

int bfs() {
    vector<vector<vector<bool>>> visited(N+1, vector<vector<bool>>(M+1, vector<bool>(2, false)));
    queue<pair<pair<int,int>, pair<int,int>>> q;

    q.push({{1,1}, {1,0}});
    visited[1][1][0] = true;

    while(!q.empty()) {
        //@현 위치
        int cy = q.front().first.first;
        int cx = q.front().first.second;
        //@경로 상의 정점 갯수
        int cnt = q.front().second.first;
        //@부순 벽 갯수
        int destroy = q.front().second.second;
        q.pop();

        if(cy == N && cx == M) return cnt;

        //@전형적인 미로 찾기 유형의 BFS
        for(int i=0; i<4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if(ny < 1 || ny > N || nx < 1 || nx > M) continue;
            //@탐색 성공1: 인접 정점의 '벽'존재 확인 + 벽 부순 횟수가 0번인지 체크 -> 벽을 부수고 게속 탐색 진행
            if(board[ny][nx] == 1 && destroy == 0) {
                visited[ny][nx][1] = true;
                q.push({{ny,nx}, {cnt+1, 1}});
            }
            //@탐색 성공2: 인접 정접의 '벽'존재 확인 + 해당 위치가 다른 어떠한 경로로부터 현재 경로와 같은 상태(벽을 부수거나 혹은 안 부수거나)를 갖고 방문했는지 체크합니다.
            else if(board[ny][nx] == 0 && !visited[ny][nx][destroy]) {
                visited[ny][nx][destroy] = true;
                q.push({{ny,nx}, {cnt+1, destroy}});
            }
        }
    }
    return -1;
}

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

    cin >> N >> M;

    string line;
    for(int i=1; i<=N; ++i) {
        cin >> line;
        for(int j=1; j<=M; ++j) {
            board[i][j] = line[j-1] - '0';
        }
    }

    cout << bfs();

    return 0;
}

 

---