[C++] 백준 3055번: 탈출

🔗문제

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

3055번: 탈출

 

🖍풀이

 

std::queue<std::pair<int, int>> water;
std::queue<std::pair<int, int>> S;
std::pair<int, int> D; // 비버의 소굴은 이동하지 않는다.

• 입력을 받으면서 필요한 좌표들을 미리 저장한다. 필요한 좌표를 찾기 위해 이차원 함수를 탐색하고 싶지 않기 때문이다.
• 이동이 필요한 물과 도치를 BFS 탐색을 위해 queue에 저장한다.

 

void BFS(std::queue<std::pair<int, int>>& q, const bool isWater, bool& flag)
{
	// ... 
}

BFS 탐색 방법이 비슷하여 하나의 함수를 짜고 isWater로 구별하도록 했다.

문제를 읽어 보면 공통된 조건이 있어 이를 처리해 준다.

물과 고슴도치는 돌을 통과할 수 없다.

 

bool flag = false;
while(!flag && !S.empty())
{
    BFS(water, true, flag);
    BFS(S, false, flag);
}

또한, 문제의 조건이 있기 때문에 물 경로 탐색을 먼저 해주어야 한다.

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

 

🚩 while문에 조건 두개를 넣을 때 ||랑 && 잘 구분 하기!

물이 더 이상 갈 곳이 없다는 건 상관 없어 큐가 비든 말든 상관이 없다.

하지만 도치가 아직 D에 못 왔는데 갈 곳이 없다는 건 탈출할 수 없다는 걸 뜻한다.

 

 

🌊 물의 탐색

if(isWater)
{
    if(map[x][y] == '.') // 빈칸만 간다. 
    {
        map[x][y] = '*';
        q.push({x, y});
    }
}

• 도치가 방문 했든 말든 빈 곳이면 인접한 곳에 물이 찬다.
• 비버의 소굴을 경로에 포함하지 않는 조건이 있다.

물도 비버의 소굴로 이동할 수 없다.

 

물이 있는 곳은 queue가 알아서 돌 것이기 때문에 안 넣어도 된다.

즉, 물의 경로를 탐색할 때는 빈 칸만 queue에 넣어주고 물이 찼다는 표시를 해준다.

이렇게 해주면 물의 재방문 처리는 알아서 된다.

 

🦔도치의 탐색

if(x ==D.first && y==D.second)
{
    visited[x][y] = visited[nx][ny] + 1;
    flag = true;
    return;
}
if(visited[x][y]==0 && map[x][y] == '.')
{
    q.push({x, y});
    visited[x][y] = visited[nx][ny] + 1;
}

도치의 탐색 중 인접한 곳에 D가 있다면 탈출 성공이다!

• 인접한 곳에서 D를 확인하는 이유
  물 경로 탐색할 때 D를 확인하면 오답! 물은 절대 D에 갈 수 없기 때문이다.

인접한 곳에 방문하지 않은 빈 칸이 있다면 queue에 집어 넣어준다.

 

💾 소스

#include <iostream>
#include <queue>
#define MAX 50

int R, C;
char map[MAX][MAX];

std::queue<std::pair<int, int>> water;
std::queue<std::pair<int, int>> S;
std::pair<int, int> D;

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

bool isValid(int a, int b)
{
    if(a>=R || b>=C || a<0 || b<0)
        return false;
    return true;
}

void BFS(std::queue<std::pair<int, int>>& q, const bool isWater, bool& flag)
{
    int qSize = q.size();
    while(qSize--)
    {
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();
        
        for(int i=0; i<4; ++i)
        {
            int x = nx + dx[i];
            int y = ny + dy[i];
            
            // 돌맹이는 도치나 물이나 못 간다.
            if(!isValid(x, y) || map[x][y] == 'X')
                continue;
            
            //물의 이동
            if(isWater)
            {
                if(map[x][y] == '.')
                {
                    map[x][y] = '*'; //물
                    q.push({x, y});
                }
            }
            //도치의 이동
            else
            {
                if(x ==D.first && y==D.second)
                {
                    visited[x][y] = visited[nx][ny] + 1;
                    flag = true;
                    return;
                }
                if(visited[x][y] ==0 && map[x][y] == '.')
                {
                    q.push({x, y});
                    visited[x][y] = visited[nx][ny] + 1;
                }
            }
        }
    }//qSize
}

int main()
{
    std::cin >> R >> C;
    for(int i=0; i<R; ++i)
    {
        for(int j=0; j<C; ++j)
        {
            std::cin >> map[i][j];
            if(map[i][j] == '*')
                water.push({i, j});
            else if(map[i][j] == 'S')
                S.push(std::make_pair(i, j));
            else if(map[i][j] == 'D')
                D = std::make_pair(i, j);
        }
    }

    bool flag = false;
    while(!flag && !S.empty())
    {
        BFS(water, true, flag);
        BFS(S, false, flag);
    }
        
    if(visited[D.first][D.second] != 0)
        std::cout << visited[D.first][D.second];
    else
        std::cout <<"KAKTUS";
    
    return 0;
}