[백준][C++] 2206번: 벽 부수고 이동하기 <188>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

2206번: 벽 부수고 이동하기

생각의 흐름

이번 문제는 진짜 중요한 점을 배웠다. 그냥 단순 BFS로 생각하면 막히는 문제이다.

분명 논리적으로 맞는것 같지만, 기존 BFS 보다 한끝 더 생각해야 하는 중요한 부분이 있다.

 

핵심부터 말하면 visited[1000][1000][2] 과 같이 3차원 배열을 이용해야 한다.

 

다음 예시 input을 살펴보자.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100
답 29

만약 이 input을 2차원 배열을 통해 방문을 기록한다면,

벽을 한번도 부순적 없는 경우의 이동과 벽을 1번 부순적이 있는 경우가 충돌하여 진행 불가능 하다.

 

예를 들어 보자. 다음은 위 input을 기준으로 2차원 visited를 통해서 BFS를 돌때 발생하는 문제이다.

최단거리를 찾기 때문에 BFS를 순회해야 하는데,

이때 2차원 배열로 방문을 확인하면 빨간 지점에서 벽을 1번 부순경우 와 벽을 부순적 없는 경우가 충돌이 난다.

 

논리적으로 생각했다면 이둘은 서로 같은 지점을 방문해도 진행이 가능해야 한다.

서로 다른 경우이기 때문이다.

 

따라서 3차원 배열을 상용하는 것 이다.

기존의 2차원 배열 평면을 2층으로 만든다고 생각하자!

1층은 벽을 부순적 없을때만 사용하고, 2층은 벽을 부순적이 있을때만 사용하도록 하는 것 이다.

이러면 같은 지점에서 서로 접해도, 멈추지 않고 각자의 길을 더 탐색하게 된다.

 

이점이 이 문제가 주는 가장 큰 교훈이자 핵심이다.

 

나머지는 그냥 BFS를 진행하면 된다. 코드는 다음과 같다.

 

보통 x, y, 부순벽의수, 이동한 칸의 수를 pair로 묶어 사용하시던데...

변수를 4개나 사용해야 하는 시점이라면, struct나 class를 사용하는게 훨씬 편하다.

 

나의 코드

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

class Position{
private:
    int x;
    int y;
    int cnt;
    int breakWallCnt;
public:
    Position(int x, int y, int cnt, int breakWallCnt) : x(x), y(y), cnt(cnt), breakWallCnt(breakWallCnt) {}

    int getX() const {return x;}
    int getY() const {return y;}
    int getCnt() const {return cnt;}
    int getBreakWallCnt() const {return breakWallCnt;}
};

int N, M;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int MAP[MAX][MAX];
bool visited[MAX][MAX][2];

void BFS(int stX, int stY){
    queue<Position> Q;
    Q.push(Position(stX, stY, 1, 0));
    visited[stX][stY][0] = true;

    while(!Q.empty()){
        int nowX = Q.front().getX();
        int nowY = Q.front().getY();
        int nowCnt = Q.front().getCnt();
        int breakWallCnt = Q.front().getBreakWallCnt();
        Q.pop();

        if(nowX == N-1 && nowY == M-1){
            cout << nowCnt;
            exit(0);
        }

        for(int i = 0; i < 4; i++){
            int nx = nowX + dx[i];
            int ny = nowY + dy[i];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

            if(MAP[nx][ny] == 1 && breakWallCnt == 0){ // 벽이고, 이번이 처음 벽인경우
                visited[nx][ny][1] = true;
                Q.push(Position(nx, ny, nowCnt+1, breakWallCnt+1));
            }else if(MAP[nx][ny] == 0 && !visited[nx][ny][breakWallCnt]) { // 길인 경우
                visited[nx][ny][breakWallCnt] = true;
                Q.push(Position(nx, ny, nowCnt+1, breakWallCnt));
            }
        }
    }
    cout << -1 << "\n";
}

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

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

    BFS(0, 0);

    return 0;
}