[ 백준 2206 ] 벽 부수고 이동하기 (C++)

백준의 벽부수고 이동하기(2206) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. BFS를 통해서 쉽게 해결할 수 있는 문제이다. 먼저 본인은 Queue에서 4가지 변수를 관리해주었다.

  { {x, y}, {벽 부순 횟수, 현재 칸수} } 이렇게 총 4가지 변수들에 대해서 관리해주었다.

2. 일반적인 BFS를 실행시키되, 벽을 부쉈는지 안부쉈는지에 대해서만 따로 확인을 해주면 되기 때문에

   탐색한 정점을 나타내는 Visit함수를 3차원 배열을 이용해서 나타내었다.

   Visit[x][y][벽을부순횟수] 이렇게 표현하였다.

   이미 방문한 정점이더라도, 벽을 부수고 왔는지, 벽을 부수지 않고 왔는지는 서로 다른 경로가 되기 때문에 저렇게 표현

   하였다.

3. BFS안에서 이동할 다음칸에 대해서도 조건을 하나 더 생각해 주어야 한다.

  1. 만약 이동하려는 다음 칸이 벽이고, 이미 벽을 한번 부셨다면?

     → 더이상 진행할 수 없다. 따라서 Queue에 넣어주지 않는다.

  2. 만약 이동하려는 다음 칸이 벽이고, 벽을 아직 부수지 않았다면?

     → 벽을 부쉈다는 표시를 해주고, Queue에 넣어서 다음 단계를 진행한다.

  3. 만약 이동하려는 다음 칸이 빈 칸이고, 벽을 한번 부수고 방문한다면?

     → 벽을 한번 부수고 방문한 정점인지 확인해주고, 아니라면 Queue에 넣어서 다음 단계를 진행한다.

  4. 만약 이동하려는 다음 칸이 빈 칸이고, 벽을 부수지 않고 방문한다면?

     → 벽을 부수지 않고 방문한 정점인지 확인해주고, 아니라면 Queue에 넣어서 다음 단계를 진행한다.

  생각해야될 게 4가지나 되는 것 처럼 보이지만, 실제로 구현해보면 그렇지 않다.

  정확한 내용은 코드를 참고하자.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
bool Visit[MAX][MAX][2];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string Inp;
        cin >> Inp;
        for (int j = 0; j < M; j++)
        {
            int Tmp = Inp[j] - '0';
            MAP[i][j] = Tmp;
        }
    }
}
 
int BFS()
{
    queue<pair<pair<int, int>, pair<int,int>>> Q;
    Q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
    Visit[0][0][0] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int B = Q.front().second.first;
        int Cnt = Q.front().second.second;
        Q.pop();
 
        if (x == N - 1 && y == M - 1)
        {
            return Cnt;
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (MAP[nx][ny] == 1 && B == 0)
                {
                    Visit[nx][ny][B+1] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(B + 1, Cnt + 1)));
                }
                else if (MAP[nx][ny] == 0 && Visit[nx][ny][B] == false)
                {
                    Visit[nx][ny][B] = true;
                    Q.push(make_pair(make_pair(nx, ny), make_pair(B, Cnt + 1)));
                }
            }
        }
    }
    return -1;
}
 
void Solution()
{
    int R = BFS();
    cout << R << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}