[Gold 3] 2206 벽 부수고 이동하기

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

 

이 문제는 BFS를 사용하면 된다.

시작 위치는 1, 1부터로 나와있지만 배열 사용의 편의 상 0,0을 시작위치로 결정하였다.

 

이 문제의 BFS의 방문 표시는 3차원 배열로 표시해야한다.

벽을 부수고 이동하는 경우와 부수지 않고 이동하는 경우가 존재하는데

벽을 1번 부시면 다음번에 벽을 만났을 때 부술 수 없기 때문이다.

// [row][column][1] == 벽을 부수지 않은 상태에서의 해당 칸에 도착하는 데에 이동한 칸의 개수 

// [row][column][0] == 벽을 부순 상태에서의 해당 칸에 도착하는 데에 이동한 칸의 개수

 

 

따라서 다음 칸이 벽이고 부술 수 있을 때면

 -벽을 부수었기 때문에 큐에 다음 칸의 좌표와 0을 넣어주고,

 -벽이 부서진 상태의 다음 칸에 도착하는 데에 이동한 칸의 개수를 넣어준다.

 

다음 칸이 벽이 아니고 아직 방문하지 않았다면

해당 칸에 벽을 부수고 왔을 때, 부수지 않고 왔을 때 각각 비교하게 된다. 

 -큐에 다음 칸의 좌표와 현재 벽을 부수었는지 상태를 그대로 넣어주고,

 -다음 칸에 현재 칸의 도착하는 데에 이동한 칸의 개수를 넣어준다.  

 

 

 

 

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

int N, M;
int answer = -1;
string graph[1001];
int visited[1001][1001][2];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs(){
    queue<pair<pair<int,int>,int>> q; // y, x, dir
    q.push({{0,0},1,});
    visited[0][0][1] = 1;

    while(!q.empty()){
        int y = q.front().first.first;
        int x = q.front().first.second;
        int block = q.front().second;
        q.pop();
        if(y == N - 1 && x == M - 1){
            answer = visited[y][x][block];
            return;
        }
        for(int i = 0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny > N - 1 || nx < 0 || nx > M -1)
                continue;
            // 벽이고 뚫을 수 있을 때
            if(graph[ny][nx] == '1' && block){
                q.push({{ny,nx},0});
                visited[ny][nx][block - 1] = visited[y][x][block] + 1;
            }
            else if(graph[ny][nx] == '0' && visited[ny][nx][block] == 0){
                q.push({{ny,nx},block});
                visited[ny][nx][block] = visited[y][x][block] + 1;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N>>M;
    for(int i = 0;i<N;i++){
        cin>>graph[i];
    }
    bfs();

    cout<<answer;
}