[백준] 3055번 탈출

문제: 3055번: 탈출

 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <set>
#include <iomanip>
#include <string.h>
#include <sstream>
#include <tuple>
#include <map>
#include <stack>
#include <queue>

using namespace std;

vector<vector<char>> world;
vector<vector<int>> visits;
queue<pair<int, int>> waterNexts;
queue<pair<int, int>> hedgehogNexts;

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

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

    int r, c;
    cin >> r >> c;
    world = vector<vector<char>>(r, vector<char>(c));
    visits = vector<vector<int>>(r, vector<int>(c));
    cin.ignore();
    for (int i = 0; i < r; i++) {
        string line;
        getline(cin, line);

        for (int j = 0; j < c; j++) {
            world[i][j] = line[j];

            if (world[i][j] == 'S') {
                hedgehogNexts.push({ i, j }); // 고슴도치 시작 위치
                visits[i][j] = 1; // 방문 처리
            }
            else if (world[i][j] == '*') {
                waterNexts.push({ i, j });
                visits[i][j] = 1; // 방문 처리
            }
        }
    }
    int time = 0;
    // 고슴도치는 물이 찰 예정인 곳으로 갈 수 없으니까 물 먼저 확장시키자
    while (!hedgehogNexts.empty()) {
        // 물 먼저 확장
        queue<pair<int, int>> newWaterNexts;
        while (!waterNexts.empty()) {
            pair<int, int> waterPos = waterNexts.front(); waterNexts.pop();

            for (int i = 0; i < 4; i++) {
                int nx = waterPos.first + dx[i];
                int ny = waterPos.second + dy[i];

                if (nx < 0 || nx > r - 1 || ny < 0 || ny > c - 1) continue;
                if (world[nx][ny] != '.') continue;   // 빈 칸이 아니면 스킵
                world[nx][ny] = '*';
                newWaterNexts.push({ nx, ny });
            }
        }
        waterNexts = newWaterNexts;

        // 고슴도치 이동
        queue<pair<int, int>> newHedgeNexts;
        while (!hedgehogNexts.empty()) {
            pair<int, int> hedgePos = hedgehogNexts.front(); hedgehogNexts.pop();
            int x = hedgePos.first;
            int y = hedgePos.second;
            if (world[x][y] == 'D') {
                cout << time;
                return 0;
            }

            for (int i = 0; i < 4; i++) {
                int nx = hedgePos.first + dx[i];
                int ny = hedgePos.second + dy[i];

                if (nx < 0 || nx > r - 1 || ny < 0 || ny > c - 1) continue;
                if (world[nx][ny] == '*' || world[nx][ny] == 'X' || visits[nx][ny] == 1) continue;

                if (world[nx][ny] != 'D') {
                    world[nx][ny] = 'S';
                }
                visits[nx][ny] = 1;
                newHedgeNexts.push({ nx, ny });
            }
        }
        hedgehogNexts = newHedgeNexts;
        time++;
    }
    cout << "KAKTUS"; // 여기까지 도달하면 고슴도치가 갈 곳이 없는거..

    return 0;
}

 

그냥 물 먼저 확장시키고 다음에 고슴도치 이동하도록 했다.