[백준] 3055: 탈출

0. 문제 주소

 

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

3055번: 탈출

 

 

1. 풀이

 

BFS 두 번 돌리는 문제.

 

잠깐 " 물 한 번 / 고슴도치 한 번 " 으로 해 볼까? 하다가 그럴 필요가 없는 걸 깨달았다.

 

 

물 먼저 각 칸 별로 걸리는 시간을 BFS를 이용해 만들어놓고,

 

다음 고슴도치도 BFS를 돌리되, 특정 칸까지 (물이 걸리는 시간 <= 고슴도치가 가는 데 걸리는 시간) 이면 갈 수 없다.

 

돌, 출발점과 도착점에는 물이 갈 수 없는 것만 잘 처리해주면 쉬운 문제

 

 

2. 풀이 코드

 

* 유의할 점

0. 코드가 너무 더럽다... 처음에 계획을 안 세우고 생각나는 대로 코드를 짜니까 정리가 안 됐다.

 

#include <bits/stdc++.h>
#define MAX 55
#define pii pair<int, int>
#define INF 987654321

using namespace std;

int grid[MAX][MAX];
int route[MAX][MAX];
int water[MAX][MAX];
bool water_visited[MAX][MAX];
int water_dist[MAX][MAX];
bool route_visited[MAX][MAX];
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};
int R, C;
pii S, D;

void W(){
    queue<pii> q;
    for (int i=1;i<=R;i++){
        for (int j=1;j<=C;j++){
            if (grid[i][j] == 1){
                q.push(pii(i, j));
            }
        }
    }

    while(!q.empty()){
        pii p = q.front();
        q.pop();
        int ci = p.first, cj = p.second;
        for (int d=0;d<4;d++){
            int ni = ci + di[d], nj = cj + dj[d];
            if (ni <= 0 || ni > R || nj <= 0 || nj > C) continue;
            if (water_visited[ni][nj]) continue;
            if (water[ni][nj] == -1){
                water[ni][nj] = 1;
                water_visited[ni][nj] = true;
                water_dist[ni][nj] = water_dist[ci][cj] + 1;
                q.push(pii(ni, nj));
            }
        }
    }
}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> R >> C;

    for (int i=1;i<=R;i++){
        string row;
        cin >> row;
        for (int j=0;j<row.size();j++){
            char curr = row[j];
            if (curr == '*'){
                grid[i][j+1] = 1;
                water[i][j+1] = 1;
            }
            else if (curr == 'X'){
                grid[i][j+1] = 2;
                water[i][j+1] = INF;
            }
            else if (curr == 'S'){
                grid[i][j+1] = 3;
                S = pii(i, j+1);
                water[i][j+1] = INF;
            }
            else if (curr == 'D'){
                grid[i][j+1] = 4;
                D = pii(i, j+1);
                water[i][j+1] = INF;
                water_dist[i][j+1] = INF;
                route[i][j+1] = INF;
            }
            else{
                water[i][j+1] = -1;
            }
        }
    }

    W();
//    for (int i=1;i<=R;i++){
//        for (int j=1;j<=C;j++){
//            cout << water_dist[i][j] << " ";
//        }
//        cout << endl;
//    }
//
//    cout << endl;

    queue<pii> Q;
    Q.push(S);
    route_visited[S.first][S.second] = true;
    while(!Q.empty()){
        pii p = Q.front();
        Q.pop();
        int ci = p.first, cj = p.second;
        for (int d=0;d<4;d++){
            int ni = ci + di[d], nj = cj + dj[d];
            if (ni <= 0 || ni > R || nj <= 0 || nj > C) continue;
            if (route_visited[ni][nj]) continue;
            if (route[ci][cj] + 1 >= water_dist[ni][nj] && water[ni][nj] != -1) continue;
            if (grid[ni][nj] == 0 || grid[ni][nj] == 4){
                route[ni][nj] = route[ci][cj] + 1;
                route_visited[ni][nj] = true;
                Q.push(pii(ni, nj));
            }
        }
    }
//
//    for (int i=1;i<=R;i++){
//        for (int j=1;j<=C;j++){
//            cout << route[i][j] << " ";
//        }
//        cout << endl;
//    }

    int ans = route[D.first][D.second];
    if (ans == INF) {
        cout << "KAKTUS";
    }
    else{
        cout << ans;
    }



    return 0;

}