[백준] 3055번 탈출 (C++)

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

 

 

이 문제는 고슴도치와 비버의 굴, 장애물, 물이존재하며 물이 시간이 지남에 따라 인접한 상하좌우로 퍼질때

고슴도치가 비버의 굴에 들어갈 수 있으면 그 최소 시간을 출력하는 문제이다.

 

고슴도치는 물이 퍼지는 곳으로 이동하지 못하기 때문에

계획을 세울때 고슴도치가 먼저 이동하고 물을 퍼지게 하도록 하였다.

만약 고슴도치가 있는 칸에 물이 퍼졌을 경우 이는 고슴도치가 못가는 것이기 때문에 처리를 해주었다.

 

따라서 고슴도치가 이동할 수 있는 칸을 탐색하는 것과 물이 이동할 수 있는 것을 탐색하는 것을 BFS를 사용하여

탐색해주었으며 만약 고슴도치가 비버 굴에 들어간 경우 시간을 출력해주었고

고슴도치를 관리하는 큐가 비었을때는 비버의 굴에 못들어가기 때문에 KAKTUS를 출력해주었다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int R, C;
char graph[51][51];
bool visited[51][51];
int startx, starty;
int endx, endy;
vector<pii> v;
queue<tuple<int, int, int>> q;

void water() {			// 물이 시간당 퍼지는 구간 찾고, 채우기
    vector<pii> tmpv;

    for(auto it : v) {
        int x = it.first;
        int y = it.second;

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

            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            if(graph[nx][ny] == 'D' || graph[nx][ny] == 'X') continue;
            if(graph[nx][ny] == '*') continue;

            tmpv.push_back({nx, ny});
            graph[nx][ny] = '*';
        }
    }
    v = tmpv;
}

void bfs() {		// 고슴도치가 갈 수있는 빈칸 찾기
    queue<tuple<int, int, int>> tmpq;
    while(!q.empty()) {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int dst = get<2>(q.front());
        q.pop();

        if(graph[x][y] == '*') continue;

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

            if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;

            if(graph[nx][ny] == 'D') {
                cout << dst + 1;
                exit(0);
            }

            if(!visited[nx][ny] && graph[nx][ny] == '.') {
                tmpq.push({nx, ny, dst+1});
                visited[nx][ny] = true;
            }
        }
    }
    q = tmpq;			고슴도치가 다음 이동했던 좌표를 다시 큐에 넣음
}

void solve() {
    while(!q.empty()) {
        bfs();
        water();
    }

    cout << "KAKTUS";
}

void input() {
    cin >> R >> C;

    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            cin >> graph[i][j];

            if(graph[i][j] == 'S') {
                startx = i, starty = j;
                q.push({i, j, 0});
                visited[i][j] = true;
            }

            if(graph[i][j] == 'D') {
                endx = i, endy = j;
            }

            if(graph[i][j] == '*') {
                v.push_back({i, j});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}