[백준][C++] 3055번: 탈출 <220>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

3055번: 탈출

생각의 흐름

기존의 BFS 알고리즘을 적용하는 문제들과는 조금 다른 점이 있는 문제이다.

 

이 문제는 두더지가 이동하는 동시에 물도 함께 차오르기 때문에 Queue를 2개 사용해야하는 문제였습니다.

물이 차오를 예정인 위치로는 두더지가 움직일 수 없기 때문에

1) 먼저 물이 차오르는 과정을 진행한 다음

2) 두더지를 이동시킴

 

또한 각각의 Queue가 empty가 될때 까지 돌리는 것 이 아니라, 해당 queue의 size만큼씩만 돌리는 것이 핵심 이였습니다.

 

예를 들어 다음 예시를 생각해봅시다.

3 3
D.*
...
.S.

만약 waterQueue가 비워질때 까지 순회해 버리면 다음과 같이 되어버린다.

3 3
D**
***
*S*

두더지는 이동 한번 못해보고 끝나버린다.

 

waterQueue의 size를 사용해보자. 맨 처음에는 size가 1이다.

waterQueue: [{0,1}]

사이즈 만큼 반복할것 이기 때문에 한번만 반복해주면 된다.

3 3
D**
..*
.S.

이후 두더지도 queue 의 사이즈, 즉 1만큼 반복해주면 된다.

3 3
D**
.S*
SSS

이런식으로 진행해나가면 됩니다!

나의 코드

#include <bits/stdc++.h>
using namespace std;

char MAP[51][51];
int cache[51][51];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int R, C;
pair<int, int> sPos, dPos;
queue<pair<int, int>> water;

void BFS() {
    queue<pair<int, int> > hedgehog;
    hedgehog.push(sPos);
    cache[sPos.first][sPos.second] = 1;

    while(!hedgehog.empty()) {
        int waterSize = water.size();
        // 물을 먼저 확장 시킨 후
        for(int k = 0; k < waterSize; k++) {
            int nowX = water.front().first;
            int nowY = water.front().second;
            water.pop();

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= R || nextY >= C) continue;
                if (MAP[nextX][nextY] == '.') {
                    MAP[nextX][nextY] = '*';
                    water.push({nextX, nextY});
                }
            }
        }
        // 고슴도치 이동
        int hSize = hedgehog.size();

        for(int k = 0; k < hSize; k++) {
            int nowX = hedgehog.front().first;
            int nowY = hedgehog.front().second;
            hedgehog.pop();

            if (nowX == dPos.first && nowY == dPos.second) {
                cout << cache[nowX][nowY] - 1;
                exit(0);
            }

            for(int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
                if (nextX < 0 || nextY < 0 || nextX >= R || nextY >= C) continue;

                if(MAP[nextX][nextY] != '*' && cache[nextX][nextY] == 0 && MAP[nextX][nextY] != 'X') {
                    cache[nextX][nextY] = cache[nowX][nowY] + 1;
                    hedgehog.push({nextX, nextY});
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;

    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            cin >> MAP[i][j];
            if(MAP[i][j] == 'S') {
                sPos.first = i;
                sPos.second = j;
            }else if(MAP[i][j] == 'D') {
                dPos.first = i;
                dPos.second = j;
            }else if(MAP[i][j] == '*') {
                water.push({i, j});
            }
        }
    }

    BFS();
    cout << "KAKTUS" << endl;

    return 0;
}