백준 16933번 벽 부수고 이동하기 3 - C++ 풀이

---

 

1. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 
2. BFS로 {1, 1, 0, 낮}인 상황 노드에서 {N, M, ?, ?}인 상황으로 가는 최단 거리를 구한다.

 

1. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 

 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다.

 

2. BFS로 {1, 1, 0, 낮}인 상황 노드에서 {N, M, ?, ?}인 상황으로 가는 최단 거리를 구한다.

 BFS를 사용해서 시작 상황에서 종료 상황까지 가는 최단 거리를 구할 수 있다. 각 노드에서 인접 노드는 상, 하, 좌, 우로 이동하는 경우 + 해당 칸에서 가만히 머무는 경우 총 5가지가 된다. 이때 인접 노드가 벽이라면 지금까지 벽을 부순 횟수와 낮밤여부를 고려해야 한다.1

 

반응형

---

#include <iostream>
#include <queue>

using namespace std;

struct Node {
    int r, c, k;
    bool night;
};

int N, M, K;
int board[1001][1001];
bool visit[1001][1001][11][2];

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int solution() {
    queue<pair<int, Node>> q;
    visit[1][1][0];
    q.push({1, {1, 1, 0, 0}});
    
    while (!q.empty()) {
        int dist = q.front().first;
        Node node = q.front().second;
        q.pop();
        
        if (node.r == N && node.c == M) return dist;
        
        for (int i=0; i<4; i++) {
            int nr = node.r + dr[i];
            int nc = node.c + dc[i];
            if (nr < 1 || nr > N || nc < 1 || nc > M) continue;
            
            if (board[nr][nc] == 0) {
                if (!visit[nr][nc][node.k][1-node.night]) {
                    visit[nr][nc][node.k][1-node.night] = true;
                    q.push({dist+1, {nr, nc, node.k, 1-node.night}});
                }
            }
            else {
                if (node.k < K && !node.night && !visit[nr][nc][node.k+1][1-node.night]) {
                    visit[nr][nc][node.k+1][1-node.night] = true;
                    q.push({dist+1, {nr, nc, node.k+1, 1-node.night}});
                }
            }
        }
        
        // 제자리에서 하루를 보내는 경우
        if (!visit[node.r][node.c][node.k][1-node.night]) {
            visit[node.r][node.c][node.k][1-node.night] = true;
            q.push({dist+1, {node.r, node.c, node.k, 1-node.night}});
        }
    }
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M >> K;
    for (int i=1; i<=N; i++) {
        string s; cin >> s;
        for (int j=1; j<=M; j++) {
            board[i][j] = s[j-1] - '0';
        }
    }
    
    cout << solution();

    return 0;
}