BOJ 3055번 : 탈출

단순 미로찾기처럼 한 점에서 마지막 점까지 찾는 BFS가 아닌, 동시에 여러 시작점에서 BFS가 적용되야하는 문제다. 물이 차기 시작하는 점이 여러곳 이기에 각자 일분마다 각각 BFS를 통해 확장해 가고, 비버 또한 일분마다 BFS를 통해 물을 피해 확장해나가야 한다.

 

미로찾기 BFS처럼 한개의 while을 통해 이 문제를 풀려고 한다면 다음 시간에 물이 찰 곳을 알지 못해 비버가 엉뚱한 위치로 이동하게 된다. 

 

이를 위해 여러개의 물, 비버의 BFS를 돌릴 여러개의 큐를 만들고, 각 시간마다 각 큐를 BFS를 통해 확장 시켜야한다.

 

입력 데이터를 받을때 몇개의 물로 차는 구역의 수를 알 수 없으므로 큐의 갯수를 미리 정할 수 없다. 이를 위해 필요시 큐를 생성하고, 각 물이 차는 지역의 큐를 모은 벡터와 비버가 이동해야하는 위치의 큐를 모은 벡터를 사용하였다.

 

vector<queue<pair<int, int>>> sq; 라는 괴상하지만 효율적인 구조를 만들어 사용하였다.

 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <utility>
 
using namespace std;
 
vector<queue<pair<int, int>>> sq; // 비버 이동 위치 y,x
vector<queue<pair<int, int>>> wq; //큐 안에 큐 넣어서 여러개 시작하는것 해결하기. 
int y_arr[4] = { -1, 1, 0, 0 }; // 위 아래 왼쪽 오른쪽
int x_arr[4] = { 0, 0, -1, 1 };
 
int Solve(int r, int c, vector<vector<char>> v, vector<vector<int>> chk) {
 
    while (!sq.empty()){
 
        for (int i = 0; i < wq.size(); i++) { // 물 차는 큐 먼저 돌기
 
            queue<pair<int, int>> tem_wq = wq[i]; // 큐 하나 꺼내옴
            queue < pair<int, int>> for_ins; // 새로 넣을 큐
            while (!tem_wq.empty()) { // 각 물 큐 다 할때까지
                int y = tem_wq.front().first;
                int x = tem_wq.front().second;
                tem_wq.pop();
 
                for (int t = 0; t < 4; t++) {
                    if ((chk[ y + y_arr[t] ][ x + x_arr[t] ] == -1) && (v[ y + y_arr[t] ][ x + x_arr[t] ] == '.')) { // 아무도 없고 바위도 없는 경우
                        chk[ y + y_arr[t] ][ x + x_arr[t] ] = 0; // 0은 물
                        for_ins.push(make_pair(y + y_arr[t], x + x_arr[t]));
                    }
                }
            }
            wq[i] = for_ins; // 새로 생성된 큐 넣어줌
        } // 물 위한 for 끝
 
    
        for (int i = 0; i < sq.size(); i++) { // 비버 이동큐
 
            queue<pair<int, int>> tem_sq = sq[i]; // 큐 하나 꺼내옴
            queue < pair<int, int>> for_ins; // 새로 넣을 큐
            while (!tem_sq.empty()) { // 각  큐 다 할때까지
                int y = tem_sq.front().first;
                int x = tem_sq.front().second;
                tem_sq.pop();
 
                for (int t = 0; t < 4; t++) {
                    if ((chk[y + y_arr[t]][x + x_arr[t]] < 0) && (v[y + y_arr[t]][x + x_arr[t]] != 'X')) { // 돌 없고 물 없는 곳
 
                        chk[y + y_arr[t]][x + x_arr[t]] = chk[y][x] + 1; 
                        if (v[ y + y_arr[t] ][x + x_arr[t]] == 'D') // 목적시 도착시
                            return chk[y + y_arr[t]][x + x_arr[t]] - 1; // 경과시간 리턴
                        for_ins.push(make_pair(y + y_arr[t], x + x_arr[t]));
                    }
                }
            }
            if (!for_ins.size()) // 더이상 비버가 이동 불가능 할 경우
                return 0;
            sq[i] = for_ins; // 새로 생성된 큐 넣어줌
        } 
    }
    return 0;
}
 
int main() {
 
    int r, c;
    cin >> r >> c;
    vector<vector<char>> v(r + 2, vector<char>(c + 2,'X')); // 미로 배열
    vector<vector<int>> chk(r + 2, vector<int>(c + 2, -1)); // 방문배열 체크
 
    for (int i = 1; i < r+1; i++) {
        for (int j = 1; j < c+1; j++) {
            cin >> v[i][j];
            if (v[i][j] == '*') {
                queue<pair<int, int>> tem_q;
                tem_q.push(make_pair(i, j));
                wq.push_back(tem_q);
                chk[i][j] = 0;
            }
            else if (v[i][j] == 'S') {
                queue<pair<int, int>> tem_q;
                tem_q.push(make_pair(i, j));
                sq.push_back(tem_q);
                chk[i][j] = 1; // 스타트 지점 표시함.
            }
        }
    }
 
    int res = Solve(r, c, v, chk);
    if (res > 0) cout << res << endl;
    else cout << "KAKTUS" << endl;
}

 

<문제>

www.acmicpc.net/problem/3055

3055번: 탈출