[Algorithm] Baekjoon 2206번 : 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

#define MAX_NUM 1000000000
 
 
struct Node
{
    int y;
    int x;
    bool hasBreakChance;
};
 
int n, m;
vector<string> arr;
int visited[1001][1001][2] = { 0 };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
int BFS()
{
    visited[0][0][0] = 1;
    visited[0][0][1] = 1;
 
    queue<Node> q;
    q.push({ 0,0,true });
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        bool curHasBreakChance = q.front().hasBreakChance; 
 
        q.pop();
 
        if (curY == n - 1 && curX == m - 1)
        {
            int answer = visited[curY][curX][curHasBreakChance];
            return answer;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= n) continue;
            if (nextX < 0 || nextX >= m) continue;
 
            if (arr[nextY][nextX] == '1') // 다음칸이 벽일 때
            {
                if (curHasBreakChance && visited[nextY][nextX][0] == 0) // 부술기회 있고 && 누가 이전에 부숴서 방문한적 없으면
                {
                    visited[nextY][nextX][0] = visited[curY][curX][1] + 1; // 
                    q.push({ nextY,nextX,false });
                }
            }
            else if (arr[nextY][nextX] == '0')// 다음칸이 빈공간일 때
            {
                if (visited[nextY][nextX][curHasBreakChance] == 0) // 누가방문한적 없으면,
                {
                    visited[nextY][nextX][curHasBreakChance] = visited[curY][curX][curHasBreakChance] + 1;
                    q.push({ nextY,nextX,curHasBreakChance});
                }
            }
        }
    }
 
    return MAX_NUM;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    string temp = "";
    int answer = MAX_NUM;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> temp;
        arr.push_back(temp);
    }
 
    answer = BFS();
 
    if (answer == MAX_NUM) cout << -1;
    else cout << answer;
}

 

BFS를 수행할 때 좀 더 생각해야할 것이 늘어난 문제이다.

기존의 방문체크를 2차원배열로만 하던것을 (2차원맵 기준), 3차원까지 확장시켜서 생각해야하는 문제.

예전에 풀었던 말이 되고픈 원숭이 문제와 비슷한 유형들의 문제인데, 오랜만에 풀어서 그런가 많이 낯설었다.

개인적인 뇌피셜론 일단 이정도 유형까지의 탐색문제는 할줄알아야 코딩테스트를 통과할 것 같다.

 

방문체크를 3차원으로 해야하는 이유는, 한 노드에 대해서 두번의 접근이 허용되기 때문이다.

1. 이전에 벽을 부숴본적 있는 노드가 탐색을 시도하려는지

2. 이전에 벽을 부숴본적 없는 노드가 탐색을 시도하려는지

 

위의 코드를 기준으로 설명을 해보겠다.

예를들어

visited[2][2][1] == 10 이라면, 벽을 부숴본적이 없는상태의 노드가 10번째에 도착했다는 뜻이다.

visited[2][2][0] == 10 이라면, 벽을 부숴본적 있던 상태의 노드가 10번째에 도착했다는 뜻이다.

 

 

일단 이점을 명심하고 퍼질때의 if문을 살펴보자

if (arr[nextY][nextX] == '1') // 다음칸이 벽일 때
{
    if (curHasBreakChance && visited[nextY][nextX][0] == 0) // 부술기회 있고 && 누가 이전에 부숴서 방문한적 없으면
    {
        visited[nextY][nextX][0] = visited[curY][curX][1] + 1; // 
        q.push({ nextY,nextX,false });
    }
}
else if (arr[nextY][nextX] == '0')// 다음칸이 빈공간일 때
{
    if (visited[nextY][nextX][curHasBreakChance] == 0) // 누가방문한적 없으면,
    {
        visited[nextY][nextX][curHasBreakChance] = visited[curY][curX][curHasBreakChance] + 1;
        q.push({ nextY,nextX,curHasBreakChance});
    }
}

 

보통의 기본적인 BFS문제들이라면 벽일 경우 탐색을 고려할 필요조차 없지만, 이번 문제에서는 조건에 따라 벽을 부수고 탐색이 가능하다. 

다만, 벽을 부술기회는 단 한번이기 때문에 현재 꺼낸 노드가 이전에 벽을 부쉈는지 여부를 체크해줘야한다.

visited[nextY][nextX][0] == 0을 체크하는 이유는, 지금 노드가 접근하려하기 이전에 이미 다른곳에서 퍼진 노드가 arr[nextY][nextX]에 이미 방문했었는지를 체크하기 위해서이다.

어차피 벽이 탐색되어지기 위해선 반드시 부숴져야되기 때문에 visited[nextY][nextX][0]값이 0인지만 체크해주면 된다.

[1]은 검사할 필요가 없다. arr[nextY][nextX]가 벽이라면, visited[nextY][nextX][1]의 값이 0에서 변경될 일은 없다.

[1]부분은 이전에 부순적이 없는 노드가 arr[nextY][nextX]를 방문했을 때 값을 업데이트하는 곳인데, 벽인곳이라면 부숴야만 들어올 수 있고, 이미 부순 시점에서 [1]부분이 아니라 [0]부분을 검사해야하기 때문이다.

 

탐색하려는 다음칸이 빈 공간이라면, 한가지만 체크해주면 된다. 이부분이 제일 중요하다고 생각 된다.

   if (visited[nextY][nextX][curHasBreakChance] == 0)

 

이게 어떤것을 의미하느냐면, 현재 arr[nextY][nextX]에 접근하려는 노드가 이전에 벽을 부순적이 있는 노드라면 visited[nextY][nextX][0]값이 0인지 체크해야할 것이다.

이전에 벽을 부순적이 없는 노드라면 visited[nextY][nextX][1]값이 0인지 체크해야할 것이다.

현재 노드가 어떤 상태인지에 따라(벽을 부순적이 있는지 없는지) arr[nextY][nextX]에 다르게 접근해야하기 때문이다.

빈 공간에 접근할 때에는 이전에 벽을 부순 노드든, 이전에 벽을 부순적이 없는 노드든 접근할 수 있기 때문에 이렇게 접근해야 한다.