백준, BOJ, 16933번, 벽 부수고 이동하기 3 : C++ [CPP]

벽을 부수다가

기다릴 줄도 알아야한다는 것이 조금 까다롭다.

 

 

https://www.acmicpc.net/problem/16933

---

 

#맞는 풀이

#include <iostream>
#include <string>
#include <queue>


#define X first
#define Y second
#define SIZE 1000

using namespace std;

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

char arr[SIZE][SIZE]; //입력
int visited[SIZE][SIZE][11]; // 0 벽을 안깼다, 1 개깼다 .. 10개 깼다.

int r, c, crush;



typedef struct Position {
    int x;
    int y;
    int wall;
    int waiting; //대기시간
    bool time; //벽을 부술 수 있는 시간인지 (낮, 밤)
}Pos;


int BFS(int _x, int _y) {
    queue<Pos> q;
    Pos p; // 처음 위치, 깬 벽 0
    p.x = _x;
    p.y = _y;
    p.wall = 0;
    p.waiting = 0;
    p.time = true;

    q.push(p);
    visited[_x][_y][0] = 1; //안 깬상태로 방문


    while (!q.empty()) {
        auto cur = q.front();
        int w = cur.wall; // 벽을 깼는지
        int wait = cur.waiting; // 대기시간
        bool isPossible = cur.time; // 낮인지 밤인지
        q.pop();

        //해당 위치 도달했으면
        if (cur.x == r - 1 && cur.y == c - 1)
            return visited[cur.x][cur.y][w]; //시작하는 칸도 포함

        


        //BFS
        for (int dir = 0; dir < 4; dir++){
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            //범위
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            //벽으로 막혀있는데 아직 벽 깰 수 있으면
            //+ visited[nx][ny][w+1] 조건이 없으면 다른 경로로 온 애도 해당 노드를 방문해서 숫자를 바꿔버리고 거기서부터 또함 ** 이게 제일 중요한 조건 **
            //낮일 때만 벽 부수기 가능
            if (arr[nx][ny] == '1' && w < crush && visited[nx][ny][w + 1] == 0 && isPossible) {

                Pos tempP;
                tempP.x = nx;
                tempP.y = ny;
                tempP.wall = w + 1;
                tempP.waiting = 0;
                tempP.time = !isPossible; //다음 노드에선 시간이 바뀜
                q.push(tempP);
                visited[nx][ny][w + 1] = visited[cur.x][cur.y][w] + 1 + wait;
            }
            //벽이 없고 현재 상태에서 방문하지 않은 곳이라면 
            //시간에 상관없이 가능
            else if (arr[nx][ny] == '0' && visited[nx][ny][w] == 0) {
                Pos tempP;
                tempP.x = nx;
                tempP.y = ny;
                tempP.wall = w;
                tempP.waiting = 0;
                tempP.time = !isPossible; //다음 노드에선 시간이 바뀜
                q.push(tempP);
                visited[nx][ny][w] = visited[cur.x][cur.y][w] + 1;
            }
            //벽을 부술 수 있지만 저녁이라 못부순다면 기다려봄
            else if (arr[nx][ny] == '1' && w < crush && visited[nx][ny][w + 1] == 0 && !isPossible) {
                Pos tempP;
                tempP.x = cur.x;
                tempP.y = cur.y;
                tempP.wall = w;
                tempP.waiting = 1;
                tempP.time = !isPossible; //다음 노드에선 시간이 바뀜
                q.push(tempP);
            }

        }
        


        
    }
    return -1;
}



int main() {
    cin >> r >> c >> crush;

    //노드입력
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            arr[i][j] = s[j];
        }
    }

    int dist = BFS(0, 0);
    cout << dist;




    return 0;
}

 

 

여기서 대기를 해야하는데

즉, 홀수번째 단계마다 낮이고 짝수번째 단계마다 밤인데

기다리는 상황이 되면 현 단계를 유지하면서 시간이 바뀌어야하는데..

즉, 벽이 있는 노드와 아닌 노드 간의 관계가 명확하지 않아서

그러한 정보 자체를 노드에 저장해놓고 갱신했다.

waiting과 time을 추가하여 해당 노드가 기다렸다면 waiting = 1이 될 것이고

time = true면 벽을 깰 수 있는 차례 (낮)이라는 소리고

아무튼 노드에 각각 저장했다.

 

3개 이상의 정보를 담을 때에는 구조체를 이용하는 것이 좋다.

**typedef 키워드를 쓰면 struct라고 하지 않아도 바로 선언이 가능하다.

 

typedef struct Position{

    ....

} Pos;