[ABC213 E] Stronger Takahashi

난이도: 1423

 

태그

• 0-1 BFS

 

풀이

1. 최단 경로 문제 같으니, 그래프를 구축해보자.

정점은 \( (r, c) \)로 잡고, 간선은 이동 가능 여부로 잡아주면 기본적인 격자 그래프를 만들 수 있습니다.

 

하지만, 이대로는 벽을 부수는 게 적용되지 않는데...

 

2. 최단 경로에서, 우리가 목표로 하는 것은?

당연하겠지만, 최단 경로 문제에서 목표로 하는 건 한 점에서 다른 점으로 가는 최단 경로를 찾는 것입니다.

 

이 문제에서는, 벽을 부수는 횟수를 최소화해야 하므로, 벽을 부수는가 여부로 간선에 가중치를 넣어볼 수 있겠네요.

하지만 \( 2 \times 2 \) 칸의 벽을 부숴야 하는데, 정확히 어떻게 해야 할까요?

 

3. \( (r, c) \)에서 벽을 부술 때 / 부수지 않을 때 이동할 수 있는 칸은?

벽을 부수지 않고 이동할 수 있는 칸은, \( (r, c) \)와 인접하면서 열려있는 칸입니다.

이렇게 이동할 때의 간선 가중치는 0이 됩니다.

 

벽을 부수고 이동할 수 있는 칸은, 아래 그림과 같이 나타낼 수 있습니다.

인접한 곳에 벽을 부수게 되면, 벽의 여부와 상관없이 4칸으로 갈 수 있다.

원래 있던 칸에 인접하게 벽을 부수는 것만 생각해봐도 되니 (미리 부숴도, 결국 인접한 칸에 도달해야 영향을 끼칠테니 그때가서 부숴도 상관없기 때문), 이를 다 생각해보면 아래와 같은 칸에 도달할 수 있다는 결론을 얻을 수 있습니다.

벽을 부수는 8가지 경우와 이 때 이동할 수 있는 칸들

이렇게 이동할 때의 간선 가중치는 1로 잡으면 됩니다.

 

코드

정점과 간선이 모두 준비되었으니, 최단 경로를 찾는 알고리즘을 돌려주면 됩니다.

이 문제의 경우, 간선 가중치가 0 또는 1이니 0-1 BFS를 사용할 수 있습니다.

char mp[520][520];
int dis[520][520];
 
void Main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){ cin >> mp[i][j]; }
    }
    deque<pi3> dq; dq.push_back({ {1, 1}, 0 });
    memset(dis, 0x3f, sizeof(dis)); dis[1][1] = 0;
    while (!dq.empty()){
        pi3 p = dq.front(); dq.pop_front();
        int y = p.fr.fr, x = p.fr.sc, dst = p.sc;
        //cout << "DQ " << y << ' ' << x << ' ' << dst << endl;
        if (y==n && x==m){ cout << dst; return; }
        if (dis[y][x] != dst){ continue; }
        for (int d = 0; d < 4; d++){
            int yy = y+dy[d], xx = x+dx[d];
            if (1 > yy || yy > n || 1 > xx || xx > m){ continue; }
            if (mp[yy][xx] == '#'){ continue; }
            if (dis[yy][xx] <= dst){ continue; }
            dq.push_front({ {yy, xx}, dst }); dis[yy][xx] = dst;
        }
        for (int dy = -2; dy <= 2; dy++){
            for (int dx = -2; dx <= 2; dx++){
                if (abs(dy*dx) == 4){ continue; }
                int yy = y+dy, xx = x+dx;
                if (1 > yy || yy > n || 1 > xx || xx > m){ continue; }
                if (dis[yy][xx] <= dst+1){ continue; }
                dq.push_back({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
            }
        }
    }
}