백준 2206 벽 부수고 이동하기

BFS를 사용해 맵을 탐색하는 문제이다. 단순히 출발지에서 도착지까지 탐색하는것에 더해, 우리의 플레이어는 원래는 가지 못하는 벽을 한번 부수고 통과할 수 있다.(이하 슈퍼파워) 이 부분에 있어서 살짝 꼬여진 문제라고 볼 수 있다.

 

일반 BFS 탐색 코드와 달라지는 점은, visited 배열이 달라진다는것과 큐에 넣을때 두 가지 조건(벽을 부수는 경우, 아닌 경우)을 따져야 한다는 점이다.

 

visited[0 or 1][N][M] 배열은, N*M 크기 맵에서 해당 픽셀을 벽을 부수고 나서 도달하였는가(1), 벽을 부수지 않고 도달하였는가(0)을 의미한다. 해당 visited 배열을 보고, 큐에 넣을 때의 조건을 따진다.

다음 방문 픽셀이 벽이고, 벽을 부술 수 있으며, 벽을 부수고 방문하지 않은 경우 -> visit에 표시하고 이제 벽을 부수지 못한다 표시한뒤 큐에 넣는다

다음 방문 픽셀이 빈 공간이고, 현재 슈퍼파워 여부로 방문하지 않은 경우 -> visit에 표시하고 현재 슈퍼파워 여부를 유지한채 큐에 넣는다.

 

Visit 배열 처리가 1차원이 늘어 생각할 부분이 있다. 벽을 만났을 때 봐야 할 visit는 무조건 1(벽 부수고 방문)이고, 그 외의 일반 탐색 시 봐야 할 visit는 당시 슈퍼파워여부로 visit배열을 보면 된다.

---

#include <iostream>
#include <string>
#include <queue>
#include <string.h>

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

typedef struct point
{
    int x;
    int y;
    int cost;
    bool superpower;
    point(int y, int x, int cost, bool superpower) : x(x), y(y), cost(cost), superpower(superpower) {}
} point;


int main()
{
    int N, M;
    std::cin >> N >> M;
    int map[N][M];
    int visited[2][N][M];

    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < N; i++)
    {
        std::string inp;
        std::cin >> inp;
        for (int j = 0; j < M; j++)
            map[i][j] = inp[j] - '0';
    }

    // for (int i = 0; i < N ; i++)
    // {
    //     for (int j = 0; j < M; j++)
    //         std::cout << map[i][j];
    //     std::cout << "\n";
    // }

    std::queue<point> q;

    q.push(point(0, 0, 1, 1));
    visited[0][0][0] = 1;
    visited[1][0][0] = 1;
    while(!q.empty())
    {
        point cur = q.front(); 
        q.pop();
        if (cur.x == M - 1 && cur.y == N - 1)
        {
            std::cout << cur.cost;
            return 0;
        }
        
        for (int i = 0; i < 4; i ++)
        {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || nx >= M || ny < 0 || ny >= N )
                continue;
            else{
                if (map[ny][nx] && cur.superpower && !visited[1][ny][nx])
                {
                    visited[1][ny][nx] = 1;
                    q.push(point(ny, nx, cur.cost+1, 0));
                }
                else if (!map[ny][nx] && !visited[!cur.superpower][ny][nx])
                {
                    visited[!cur.superpower][ny][nx] = 1;
                    q.push(point(ny, nx, cur.cost+1, cur.superpower));
                }
            }


        }
        
    }
    std::cout << -1;
}

BFS에 대해 이제 조금씩 알아가는 것 같다. LCA와 다르게 응용이 한없이 많아질 수 있을 것 같다. 차근차근히 문제들 봐봐야겠다.

 

오늘도 평온한 하루가 되길. 슨민.