3055. 탈출

백준 3055번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

3055번: 탈출

풀이

아이디어

무언가 퍼지는 느낌이고 (여기서는 물이) 여러 방향으로 가는 무언가가 (여기서는 고슴도치가) 목적지에 도달할 수 있는 최단 시간을 구하는 것이기 때문에 어렵지 않게 BFS를 떠올릴 수 있었다. 최단시간만 구하는 문제였다면 DFS를 사용해도 되었겠지만 여기서는 물도 함께 퍼지기 때문에 DFS로는 풀지 못하거나 풀 수 있더라도 복잡한 방법이 될 것 같다.

문제를 확인해 보면 매 초마다 물이 4방향으로 퍼지고, 고슴도치가 4방향으로 움직일 수 있다. 물과 고슴도치의 움직임에 각각 BFS를 적용해서 물 먼저 움직인 후에, 고슴도치를 움직여주는 방법으로 문제를 해결했다. 물을 먼저 움직인 이유는 고슴도치가 움직일 방향에 물이 찰 예정인 경우 일때는 그 쪽으로 움직일 수 없다고 해서 처리의 용이성을 위해서 물을 먼저 이동시켜주었다. 사실 같은 BFS이기 때문에 큐를 하나만 두고 움직이는 방법도 있는 듯 한데… 큐를 두개 두는 편이 좀 더 이해하기 쉬운 것 같아서 그냥 2개 두는 방법만 생각해 보았다.

코드

#include <iostream>
#include <queue>
#include <utility>
#include <queue>
using namespace std;

//pair first: 행 second: 열
int cnt;
char map[50][50];
queue<pair<int, int>> s_queue;	// s(고슴도치) 큐
queue<pair<int, int>> water;	// 물 큐
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};
int r, c;

void water_move(){
    pair<int, int> curr;
    pair<int, int> new_w;
    int size = water.size();
    for(int i = 0; i < size; i++){
        curr = water.front();
        water.pop();
        for(int dir = 0; dir < 4; dir++){
            new_w = {curr.first + dy[dir], curr.second + dx[dir]};
            if(new_w.first < 0 || new_w.second < 0 || new_w.first > r || new_w.second > c || map[new_w.first][new_w.second] != '.')
                continue;
            map[new_w.first][new_w.second] = '*';
            water.push(new_w);
        }
    }
}

void bfs(){
    pair<int, int> curr_s;
    pair<int, int> new_s;
    while (!s_queue.empty()){
        cnt++;
        water_move();
        int size = s_queue.size();
        for (int i = 0; i < size; i++){
            curr_s = s_queue.front();
            s_queue.pop();
            for(int dir = 0; dir < 4; dir++){
                new_s = {curr_s.first + dy[dir], curr_s.second + dx[dir]};
                if (map[new_s.first][new_s.second] == 'D'){
                    cout << cnt;
                    return;
                }
                if(new_s.first < 0 || new_s.second < 0 || new_s.first > r || new_s.second > c || map[new_s.first][new_s.second] != '.')
                    continue;
                map[new_s.first][new_s.second] = '*';
                s_queue.push(new_s);
            }
        }
    }
    cout << "KAKTUS";
    return;
}

int main(){
    cin >> r >> c;
    cnt = 0;
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            cin >> map[i][j];
            if (map[i][j] == 'S')
                s_queue.push({i, j});
            else if (map[i][j] == '*')
                water.push({i, j});
        }
    }
    bfs();
}