[백준] 14442 벽 부수고 이동하기 2

14442번: 벽 부수고 이동하기 2

문제 확인

 

경로 탐색 문제입니다.

단순 dp로 풀 수 있지만 최대 경우의 수 dp[10][1000][1000] 보다 bfs, 가지치기가 경우의 수가 적으므로 bfs으로 풉니다.

 

풀이

 

문제에서 핵심은 벽을 부수는 경우 최단경로가 달라질 수 있다는 점입니다.

따라서 벽을 부순 횟수에 따라 방문했던 칸을 다시 방문할 수 있으므로 다음과 같이 풀 수 있습니다.

• 처음 방문 : 현재 벽을 부순 횟수 k를 기록합니다.
• n번째 방문 : 기록된 k 횟수보다 큰 경우 이전 방문에서 최단경로를 찾을 수 있기 때문에 넘어가고 k보다 작은 경우 최단경로가 달라질 수 있으므로 기록하고 bfs 탐색을 합니다.

 

기존 bfs와 다르게 visited 배열을 int로 선언하고 depth를 따로 노드마다 적용하지 않고 bfs 특성을 이용해 한 번의 큐 전체 루프가 끝나면 depth를 증가시킵니다.

while( que : empty ){
	현재 큐 크기 기록;
	while ( 기록된 큐 크기 만큼 ) {
	    que pop()
	    if( 목적지 )
	        print depth, 종료;
	    for( 4개 방향 ){
	        if( 현재 벽을 부순 횟수 < visited에 기록된 벽을 부순 횟수)
	    	    go next
	    }
    }
    depth++;
}

 

코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef struct node {
    int x, y, k;
    node(int x, int y, int k) :x(x), y(y), k(k) {};
 
}node;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    char ary[1002][1003] = { 0 };
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> (ary[i] + 1);
 
 
    int visited[1001][1001];
    memset(visited, 0x7f, sizeof visited);
    visited[1][1] = 0;
 
    int dx[] = { 0, 1, 0, -1 },
        dy[] = { 1, 0, -1, 0 }, depth = 1;
    queue<node> que;
    que.emplace(1, 1, 0);
 
    while (!que.empty()) {
 
        int cur_size = que.size();
        while (cur_size--) {
            auto cur = que.front();
            que.pop();
 
            if (cur.x == n && cur.y == m) {
                cout << depth;
                return 0;
            }
            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d], ny = cur.y + dy[d];
                if (!ary[nx][ny]) continue;
                if (cur.k < visited[nx][ny]) {
                    if (ary[nx][ny] != '1') {
                        visited[nx][ny] = cur.k;
                        que.emplace(nx, ny, cur.k);
                    }
                    else if (cur.k < k) {
                        visited[nx][ny] = cur.k + 1;
                        que.emplace(nx, ny, cur.k + 1);
                    }
                }
            }
        }
 
        depth++;
    }
    cout << -1;
}