[백준] 2206 : 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

---

• 벽을 하나 깰 수 있다는 점을 제외하면 BFS 대로 풀면 된다.
• 여기다가 벽을 하나 깬다는 조건을 넣기 위해서는 큐에다가 자신의 현재위치와 벽을 부쉈는지 여부를 추가해주면 된다.
• 벽을 부신 상태에서 이동하는지, 안 부시고 이동 중인지 확인이 가능하다면 딱 하나만 부신 상태로 이동이 가능하다.
• visited 배열을 관리할 때, 벽을 부신 상태와 부시지 않은 상태에 대해서 따로 처리를 해주어야 한다.
• 벽을 부신 다음 방문 처리를 해주면서 올 경우, 부시지 않고 오던 노드들은 방문 처리 되었다고 생각하여 제외된다.
• 하지만 부시지 않은 방문자들은 이후에 벽을 부실 수 있는 여지가 남아 있기 때문에 해당 노드를 검사할 필요가 있기 때문에, 두 방문 배열을 따로 저장하고 큐에서 처리할 때도 나눠서 처리해준다.

---

#include <iostream>
#include <queue>

using namespace std;

int n, m;
char map[1001][1001];
bool visited[1001][1001];           // 벽을 안 깨고 온 방문자들과
bool broke_visited[1001][1001];     // 벽을 꺠고 온 방문자들에 대해서 따로 관리
int dir[4] = {1, -1, 0, 0};
int answer = 10e8;

int bfs()
{
    if(n == 1 && m == 1) return 1;
    visited[1][1] = true;
    queue<pair<pair<int,int>, bool>> q;             // 현재 위치와 벽을 깬 상태인지에 대해서 저장
    q.push({{1,1}, false});                         // (1,1) 에서 벽 안 깬 상태로 출발

    int d = 1;                                      // 시작점도 거리에 포함
    while(q.size())
    {
        int sz = q.size();
        for(int i = 0 ; i < sz ; i++)                               // 현재 거리에 있는 노드들에 대해서 확인
        {
            pair<pair<int, int>, int> cur = q.front();
            q.pop();
            for(int k = 0 ; k < 4 ; k++)                            // 노드마다 4방향 확인해서
            {
                int nextR = cur.first.first + dir[k];
                int nextC = cur.first.second + dir[3-k];
                bool has_broken = cur.second;
                if(nextR == n && nextC == m) return d+1;
                if(nextR > 0 && nextR <= n && nextC > 0 && nextC <= m)
                {
                    if(has_broken)                                  // 이미 벽을 꺠고 온 상태라면
                    {
                        if(map[nextR][nextC] == '1')                // 벽에 마주칠 경우 두개는 못 뚫으니 스킵
                        {
                            continue;
                        }
                        else if(!broke_visited[nextR][nextC])       // 하지만 다른 벽을 깨고 온 노드가 방문하지 않았다면
                        {
                            broke_visited[nextR][nextC] = true;     // 처리해주고 큐에 넣어줌
                            q.push({{nextR, nextC}, true});
                        }
                    }
                    else                                            // 벽을 깨지 않은 상태라면
                    {
                        if(map[nextR][nextC] == '1')                // 벽을 만났을 때
                        {
                            has_broken = true;                      // 벽을 깨주고 깬 방문자로 처리
                            broke_visited[nextR][nextC] = true;
                            q.push({{nextR, nextC}, true});
                        }
                        else if(!visited[nextR][nextC])             // 그 외에는 일반 방문자로 처리
                        {
                            visited[nextR][nextC] = true;
                            q.push({{nextR, nextC}, false});
                        }
                    }
                }
            }
        }
        d++;
    }
    return -1;
}

int main(void)
{
    cin >> n >> m;
    for(int r = 1 ; r <= n ; r++)
    {
        for(int c = 1 ; c <= m ; c++)
        {
            cin >> map[r][c];
            visited[r][c] = false;
            broke_visited[r][c] = false;
        }
    }
    
    cout << bfs() << endl;
}