[백준][3055번] 탈출[cpp, c++]

백준 3055번 탈출

• BFS + 시뮬레이션 문제였다.
• https://www.acmicpc.net/problem/3055

3055번: 탈출

• 풀이 방법
  1) 시뮬레이션을 생각하면, 고슴도치 이동 - > 물이 차오름, 을 구현하면 된다. 생각보다 까다로웠다.

  (물이 먼저 차오르는지 알고 잠깐 헷갈렸었는데, 고슴도치 먼저 이동시키면 된다.) 

  2) 고슴도치가 이동할 수 있는 부분 bfs, 물이 차오를 수 있는 bfs로 한 단계 bfs씩 해줘야한다.
  3) 이를 구현하기 위해, push부분을 bfs 부분 밖에 빼줘서 해결했다.

• 함수 설명
  1) input_data() : 입력 받음
  2) water_bfs(): 일반적인 bfs 코드이지만, 큐에 push하는 부분이 빠져있다. 방문한 곳을 * 로 바꿔준다.
  3) bfs(): 고슴도치의 bfs 코드이지만, 역시 큐에 push하는 부분이 빠져있다. 집을 발견하면 탈출한다.
  4) sol(): 고슴도치, 물의 BFS코드를 1번 돌리고, PUSH해주는 부분이다. 둘 다 PUSH 해줄 게 없으면 KAKTUS를 출력한다.

#include <iostream>
#include <queue>
using namespace std;
int R, C;
char map[51][51];
int nx[4] = { 1,0,-1,0 };
int ny[4] = { 0,1,0, - 1};
bool water_check[51][51];
int check[51][51];
int flag;
int ans;
queue<pair<char, char>> wq;
queue<pair<char, char>> q;

void input_data() { //입력
    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') q.push(make_pair(i, j));
            else if (map[i][j] == '*') wq.push(make_pair(i, j));
        }
    }
}

void water_bfs() { //물 bfs    
    while (!wq.empty()) {
        int x = wq.front().first;
        int y = wq.front().second;
        water_check[x][y] = true;
        wq.pop();
        for (int i = 0; i < 4; i++) {
            int dx = x + nx[i];
            int dy = y + ny[i];
            if (dx >= R || dx < 0 || dy >= C || dy < 0) continue;
            if (map[dx][dy] == 'X' || map[dx][dy] == 'D') continue;
            map[dx][dy] = '*';
        }
    }
}

void bfs() { // 고슴도치 bfs
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        check[x][y] = 1;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int dx = x + nx[i];
            int dy = y + ny[i];
            if (map[dx][dy] == 'D') {
                cout << ans+1 << "\n";
                flag = 1;
                return;
            }
            if (dx >= R || dx < 0 || dy >= C || dy < 0) continue;
            if (map[dx][dy] != '.') continue;
            map[dx][dy] = 'S';
        }
    }
}

void sol() {
    while (1) {
        int f1 = 0;
        int    f2 = 0;
        if (!q.empty()) {
            bfs();
            ans++;
        }
        if (!wq.empty()) water_bfs();
        if (flag == 1) break; //flag가 1이면, 집을 찾은 것

        //push하는 부분
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (map[i][j] == '*' && water_check[i][j] == false) {
                        wq.push(make_pair(i, j));
                        f1 = 1;
                    } 
                    else if (map[i][j] == 'S' &&check[i][j] == 0) {

                        q.push(make_pair(i, j));
                        f2 = 1;
                    }
                }
            }
            if (f1 == 0 && f2 == 0) {
                cout << "KAKTUS" << "\n";
                break;
            } 
        }


}

int main(void){
    input_data();
    sol();
    return 0;
}