백준, BOJ, 3055번, 탈출 : C++ [CPP]

 

이 문제 어렵다기 보다.

조건이 진짜 많아서 내 몸에 해롭다.

 

 

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

 

 

---

 

#맞는 풀이

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <climits>

#define X first
#define Y second

using namespace std;


int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };



int water[50][50]; // 물이 가는길
int man[50][50]; // 사람이 가는 길

int R, C;

int main() {

    cin >> R >> C;

    int sx, sy; //시작위치
    int ax, ay; //도착해야하는 위치

    //man, water -1로 초기화.
    for (int i = 0; i < R; i++) fill(man[i], man[i] + C, 0);
    for (int i = 0; i < R; i++) fill(water[i], water[i] + C, INT_MAX);
    // 물은 초기화를 최댓값으로 하는 게 낫다.. (도달하지 않은 부분은 최댓값으로..)이것때문에 1시간날림
    
    

    vector <pair<int, int>> vec;

    
    //입력 받음
    for (int i = 0; i < R; i++) {
        string s;
        cin >> s;
        
        for (int j = 0; j < C; j++){
            if (s[j] == 'D') {
                ax = i;
                ay = j;
            }
            else if (s[j] == 'S'){
                sx = i;
                sy = j;
            }
            else if (s[j] == 'X') {
                man[i][j] = -1; //벽
            }
            else if ( s[j] == '*'){
                //물의 위치
                vec.push_back({i, j});
                man[i][j] = -1; //갈 수 없는
            }
        }
    }


    //최단거리므로 BFS로 찾아보겠다.
    //시간에 따른 물 위치 설정
    queue <pair<int, int>> q;
    for (auto v : vec) {
        q.push(v);
        water[v.X][v.Y] = 0; //물 시작점.
    }

    vec.clear();

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if (nx == ax && ny == ay) continue; // 비버집은 물이 안셈
            if (nx < 0 || nx >= R || ny < 0 || ny >= C)continue;
            if (water[nx][ny] != INT_MAX) continue; //방문했으면 continue;
            if (man[nx][ny] == -1)continue; // 돌엔 물 안참
            q.push({ nx,ny });
            water[nx][ny] = water[cur.X][cur.Y] + 1; // 해당 시간에 물이 있음.(방문처리)
        }
    }


    //물이 이동 다했으면 이제 사람차례
    //q는 비어있으니 재활용

    q.push({ sx,sy });
    man[sx][sy] = 0;

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if (nx < 0 || nx >= R || ny < 0 || ny >= C)continue; //범위 
            if (man[nx][ny] != 0) continue; //방문했으면 continue;
            if (man[nx][ny] == -1)continue; // 돌이나 물이 있는 노드는 못지나감
            if (water[nx][ny] <= man[cur.X][cur.Y] + 1) continue;
            //내가 해당 노드에 도착할 시간이 water랑 겹치면못감
            q.push({ nx,ny });
            man[nx][ny] = man[cur.X][cur.Y] + 1; // 해당 시간에 지나갈 수 있음.(방문처리)
        }
    }


    //만약 비버 집의 man 노드가 0이 아니라면 도착했고 최단시간임.

    if (man[ax][ay] != 0) {
        cout << man[ax][ay];
    }
    else {
        cout << "KAKTUS";
    }

}

 

 

여기서 MAP을 받지 않아도

사람이 갈 수 있는 길

물이 갈 수 있는 길을 구분만 해줘도 된다.

 

또한 INT_MAX로 water를 초기화 한 것은 

water 자체를 시간에 따른 물로 봤기 때문이다.