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

출처 : 3055번: 탈출 (acmicpc.net)

3055번: 탈출

풀이 방법

입력받을 때부터 S와  D 지점의 좌표를 기록하고 water의 좌표 벡터에 기록하였다

BFS를 시작할 때 queue에 water의 좌표를 먼저 추가 해준 후 고슴도치의 위치를 que에 넣어 주었는데

이유는 water을 먼저 BFS 하고 그 길을 고슴도치가 갈 수 있냐 없냐 판단을 하기 위해서 이다 

(고슴도치를 먼저 이동시키면 동시에 물이 들어오는 경우 복잡해짐)

그런 후 BFS를 돌며 다음 좌표의 board(땅) 값이 '.' 이면 물 또는 고슴도치를 이동시켰다.

이때 만약 고슴도치라면 2차원 배열 cnt를 만들어 주어서 몇 초가 지났는지 기록해 주었다.

BFS로 탐색하다 D지점이 나오면 이전 좌표의 cnt 값에 + 1을 더해서 리턴해주었다

BFS가 끝날 때까지 D지점이 나오지 않으면 return 0을 하여 답이 없음을 표시했다

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int R, C;
int visited[51][51];
int cnt[51][51];
int startX, startY;
vector<pii> water;
int endX, endY;
vector<string> board;

// 물 먼저 퍼트리고 고슴도치 이동
int BFS() {
    queue<pii> que;
    for (int i = 0;i < water.size();i++) {
        que.push(make_pair(water[i].first, water[i].second));
    }
    que.push(make_pair(startY, startX));

    while (!que.empty()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
        for (int i = 0;i < 4;i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            if (nextY >= 0 && nextY < R && nextX >= 0 && nextX < C) {
                if (nextX == endX && nextY == endY) { // 고슴도치의 도착
                    if (board[y][x] == 'S') return cnt[y][x] + 1;
                }
                if (board[nextY][nextX] == '.') { // 물 또는 S의 확산
                    if (board[y][x] == 'S') {
                        cnt[nextY][nextX] = cnt[y][x] + 1;                        
                    }
                    board[nextY][nextX] = board[y][x];                        
                    que.push(make_pair(nextY, nextX));
                }                
            }
        }
    }
    return 0;
}


int main() {
    cin >> R >> C;
    memset(visited, 0, sizeof(visited));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0;i < R;i++) {
        string st;
        cin >> st;
        for (int k = 0;k < C;k++) {
            if (st[k] == 'S') {
                startX = k;
                startY = i;
            }
            if (st[k] == 'D') {
                endX = k;
                endY = i;
            }
            if (st[k] == '*') {
                water.push_back(make_pair(i, k)); // y, x
            }
        }
        board.push_back(st);
    }
    int ans = BFS();
    if (ans == 0) cout <<"KAKTUS";
    else cout << ans;
    return 0;
}