[C++] 백준 BOJ 3055 탈출

문제링크 : https://boj.kr/3055

BFS를 이용하여 풀이한 시뮬레이션 문제이다.

다른 사람들 이야기를 들어보면 굳이 BFS를 이용하고 풀지 않아도 되는 것 같다.

(물이 차오르는 시간들을 저장한 배열을 따로 만들면 되는듯 하다.)

아무튼 이 풀이는 BFS!!

BFS로 풀이를 고려한다면

1. 고슴도치가 비버굴을 찾기 위한 BFS

2. 물이 차오르는 BFS

동시에 2개의 BFS를 돌려야 한다.

하지만, 문제의 조건에서 '고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.'라고 하였기 때문에

물이 차오르는 BFS를 먼저 선행하고 고슴도치의 BFS를 후행하는 식으로 돌리면 된다.

그렇게 하기 위해선 같은 큐 안에 '물'을 먼저 넣어서 돌리고 '고슴도치'를 뒤이어서 넣으면 된다.

입력시 물일 경우 큐에 넣고 고슴도치는 따로 저장해둔다.

'물' BFS가 먼저 선행되어야하기 때문이다.

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        cin >> arr[i][j];
        if (arr[i][j] == 'S') {
            go = {'S', i, j, 0}; // 고슴도치
            visited[i][j] = true;
            arr[i][j] = '.'; // 고슴도치 자리를 빈공간으로
        } else if (arr[i][j] == '*')
            Q.push({'*', i, j, 0}); // 물을 큐에 넣음
    }
}

현재의 노드가 '물'이고 인접 노드가 '빈공간'일 경우 물이 차오를 수 있는 조건이 성립한다.

if (cur.type == '*' && arr[nx][ny] == '.') {
    arr[nx][ny] = '*';
    Q.push({'*', nx, ny, cur.t + 1});
}

현재의 노드가 '고슴도치'이고 인접 노드가 '빈공간'이면서 방문하지 않았을 경우 고슴도치의 이동이 가능하다.

else if (cur.type == 'S' && arr[nx][ny] == '.'
         && !visited[nx][ny]) {
    visited[nx][ny] = true;
    Q.push({'S', nx, ny, cur.t + 1});
}

현재의 노드가 '고슴도치'이고 인접 노드에 '비버굴'이 있다면 결과를 출력한다.

// 고슴도치면서 비버굴
else if (cur.type == 'S' && arr[nx][ny] == 'D') {
    cout << cur.t + 1;
    exit(0);
}

고슴도치가 이동할 수 없는 위치일 경우를 나타낸 조건문이다.

사실 이 문장은 제외하여도 결과를 도출하는 데에는 전혀 상관 없다.

다만, 고슴도치가 더 이상 이동하지 못하는 시점에 바로 탈출하기 때문에 시간을 먼지만큼 줄일 수 있다.

// 현재 큐가 물인데 다음 큐가 고슴도치가 아니면서
// 시간대는 다음 단계라면
// == 고슴도치가 큐에서 아예 사라졌을 때
// == 더 이상 고슴도치가 이동할 곳이 없을 때
if (cur.type == '*' && Q.front().type != 'S'
    && (cur.t < Q.front().t)) {
    cout << "KAKTUS";
    exit(0);
}

큐에서 출력이 안되었을지도 모르므로 return 전에 "KAKTUS" 출력 구문을 넣어줬다.

    cout << "KAKTUS";
 
    return 0;
}

// BOJ 3055 탈출
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
 
struct pt {
    char type; // S = 고슴도치 * = 물
    int x, y, t;
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    // . 비어있는곳
    // * 물차있는곳
    // X 돌
    // D 비버굴 (목적지)
    // S 고슴도치
 
    int N, M;
    cin >> N >> M;
    vector<vector<char> > arr(N + 2, vector<char>(M + 2, 'X'));
    vector<vector<bool> > visited(N + 2, vector<bool>(M + 2, false));
 
    pt go; // 고슴도치
    queue<pt> Q;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'S') {
                go = {'S', i, j, 0}; // 고슴도치
                visited[i][j] = true;
                arr[i][j] = '.'; // 고슴도치 자리를 빈공간으로
            } else if (arr[i][j] == '*')
                Q.push({'*', i, j, 0}); // 물을 큐에 넣음
        }
    }
    // 고슴도치 큐에 넣음
    Q.push(go);
 
    while (!Q.empty()) {
        pt cur = Q.front();
        Q.pop();
        int x = cur.x;
        int y = cur.y;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 물일 경우
            if (cur.type == '*' && arr[nx][ny] == '.') {
                arr[nx][ny] = '*';
                Q.push({'*', nx, ny, cur.t + 1});
            }
            // 고슴도치일 경우
            else if (cur.type == 'S' && arr[nx][ny] == '.'
                     && !visited[nx][ny]) {
                visited[nx][ny] = true;
                Q.push({'S', nx, ny, cur.t + 1});
            }
            // 고슴도치면서 비버굴
            else if (cur.type == 'S' && arr[nx][ny] == 'D') {
                cout << cur.t + 1;
                exit(0);
            }
        }
 
        // 현재 큐가 물인데 다음 큐가 고슴도치가 아니면서
        // 시간대는 다음 단계라면
        // == 고슴도치가 큐에서 아예 사라졌을 때
        // == 더 이상 고슴도치가 이동할 곳이 없을 때
        if (cur.type == '*' && Q.front().type != 'S'
            && (cur.t < Q.front().t)) {
            cout << "KAKTUS";
            exit(0);
        }
    }
    cout << "KAKTUS";
 
    return 0;
}