[백준] 3055번: 탈출

 

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

3055번: 탈출

문제에서 최단 경로에 대해 묻는다?

너비 우선 탐색 알고리즘 문제일 확률이 높다.

이 문제 역시 BFS 문제이다.

그나저나 문제가 조금 귀엽긴 하다 ㅋㅎ

 

1. 풀이 방법

 

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

2) 고슴도치가 이동할 수 있는 부분 BFS, 물이 차오를 수 있는 BFS로 한 단계 BFS씩 해줘야 한다.

3) 이를 구현하기 위해, push부분을 BFS 부분 밖으로 빼주어서 해결하였다.

 

2. 함수 설명

 

1) inputData() : 입력 받는 함수

2) waterBFS() : 일반적인 BFS 코드이지만, 큐에 push하는 부분이 빠져있다. 방문한 곳을 *로 바꿔준다.

3) BFS() : 고슴도치의 BFS 코드이지만, 역시 큐에 push하는 부분이 빠져있다. 집을 발견하면 탈출한다.

4) sol() : 고슴도치, 물에 대한 BFS 코드를 1번 돌리고, 큐에 push해주는 부분이다. 둘 다 push 해줄 것이 없다면

"KAKTUS"를 출력한다.

 

3. 소스 코드 

#include <iostream>
#include <queue>
using namespace std;

int R, C;
const int MAX = 51;
char map[MAX][MAX];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
bool checkWater[MAX][MAX];
bool check[MAX][MAX];
int flag;
int ans;

queue<pair<char, char>> wq;
queue<pair<char, char>> q;

void inputData() { // 입력
    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 waterBFS() { // 물에 대한 BFS
    while(!wq.empty()) {
        int x = wq.front().first;
        int y = wq.front().second;
        checkWater[x][y] = true;
        wq.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C)
                continue;
            if (map[nx][ny] == 'X' || map[nx][ny] == 'D')
                continue;
            map[nx][ny] = '*';
        }
    }
}

void BFS() { // 고슴도치에 대한 BFS
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        check[x][y] = true;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (map[nx][ny] == 'D') {
                cout << ans + 1 << '\n';
                flag = 1;
                return;
            }
            if (nx < 0 || ny < 0 || nx >= R || ny >= C)
                continue;
            if (map[nx][ny] != '.')
                continue;
            map[nx][ny] = 'S';
        }
    }
}

void sol() {
    while(true) {
        int f1 = 0;
        int f2 = 0;
        if (!q.empty()) {
            BFS();
            ans++;
        }
        if (!wq.empty())
            waterBFS();
        if (flag == 1) // flag가 1이면 집을 찾았다는 의미임
            break;

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

        if (f1 == 0 && f2 == 0) {
            cout << "KAKTUS" << '\n';
            break;
        }
    }
}

int main() {
    inputData();
    sol();
    return 0;
}

 

제출 결과