3055번 탈출

역시나 틀리면 안 되는 기본적인 BFS 문제이다.

문제에서

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 

즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

라고 쓰여져 있는데,

이 뜻은 물을 먼저 queue에 push를 하고, 활용하라는 뜻이다. 코드 101 ~ 106번 째 줄

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int R = 0, C = 0;
 
int sy = 0, sx = 0; // 고슴도치 위치
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
queue<pair<int, pair<int, int> > > q;
 
bool visit[2][51][51] = { false, }; // visit[0]~ : 물, visit[1]~ : 고슴도치
 
char map[51][51];
 
int BFS()
{
    q.push({ 1, { sy, sx } }); // 고슴도치 위치 push
    
    visit[1][sy][sx] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().second.first;
            int c = q.front().second.second;
            int cur = q.front().first;
 
            q.pop();
 
            if (cur == 1 && map[r][c] == 'D') // 고슴도치(1)가 비버의 굴(D)에 도착했다면
            {
                return ret;
            }
 
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= R || x < 0 || x >= C || visit[cur][y][x]) continue;
 
                if (cur == 0) // 물
                {
                    if (map[y][x] == '.')
                    {
                        visit[cur][y][x] = true;
 
                        map[y][x] = '*'; // 물로 바뀐다.
 
                        q.push({ cur, {y,x} });
                    }
                }
                else if (cur == 1) // 고슴도치
                {
                    if (map[y][x] == '.' || map[y][x] == 'D') // 돌(X)이나 물(*)은 못 간다
                    {
                        visit[cur][y][x] = true;
 
                        q.push({ cur,{ y, x } });
                    }
                }
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
int main(void)
{
    scanf("%d %d", &R, &C);
 
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> map[i][j];
 
            if (map[i][j] == 'S')
            {
                sy = i;
                sx = j;
            }
            else if (map[i][j] == '*')
            {
                q.push({ 0, { i,j } }); // 물이므로, 0
 
                visit[0][i][j] = true;
            }
        }
    }
 
    int result = BFS();
 
    if (result == -1) printf("KAKTUS\n");
    else printf("%d\n", result);
 
    return 0;
}