[ 백준 3197 ] 백조의 호수 (C++)

백준의 백조의 호수(3197) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 물과 빙판과 백조 3개로 이루어진 맵이 주어진다. 백조가 서로 만나기 위해서는 사이에 빙판이 있으면 안되고, 물이 있어아먄

   서로 만날 수가 있다.

   물과 인접한(상하좌우로 한방향이라도 연결) 빙판은 하루가 지나면 녹아서 물이되게 된다.

   이 때, 백조가 서로 만날 수 있는 최소의 날을 구하는 것이 문제이다.

2. 풀이자체는 어렵지 않은데, 문제는 시간초과가 잘 뜨는 문제이다.

   처음 생각한 풀이 법은, 맵을 복사하고 물과 인접한 빙판은 녹여주고, 백조를 움직이면서 만날 수 있는지 없는지를 판단후에

   만날 수 없는 경우, 다시 Visit배열을 초기화시키고.... 뭐 이런 식으로 풀어주었는데, 시간초과가 났다.

   시간초과를 해결하기 위해서 Visit배열을 초기화 시키는 부분을 없앴고, Queue를 더 많이 사용하는 방식으로 바꾸었다.

3. 구체적인 풀이에 대해서 알아보자. 먼저 이 문제에서 본인은 Queue를 총 4개를 사용했다.

   백조에 대한 현재 Queue, 백조에 대한 Next Queue, 물에 대한 현재 Queue, 물에 대한 Next Queue

   While문을 계속해서 돌리면서 백조에 대한 BFS() 한번, 물에 대한 BFS()를 한번씩 실행시킨다.

   만일, 백조에 대한 BFS()에서 백조가 서로 만나게 되면 그대로 반복문을 종료시키면 된다.

   3-1) 백조에 대한 BFS()

   - 백조가 다른 백조를 찾기 위해서 인접한 방향으로 나아갈 때

     인접한 방향이 물이라면 : 현재 Queue에 Push후 계속 진행.

     인접한 방향이 빙판이라면 : 백조의 Next Queue에 Push후 진행.

     인접한 방향이 백조라면 : 서로 만났다는 것을 Check 해준 후 종료.

     이렇게 3가지에 대해서 구현해 주면 된다.

     이 때, 일반적인 BFS와 같이 이미 탐색한 정점에 대해서는 다시 탐색하는 일이 없도록 Visit배열에 Check는 해줘야 한다.

   3-2) 물에 대한 BFS()

   - 본인은 초기에 맵을 입력 받을 때, 빙판이 아닌 지점에 대해서는 모두 물에 대한 Queue에 모두 push해 주었다.

     여기서 빙판이 아닌 지점에 대해서 모두 넣은 이유는, 빙판 근처에 물이 있거나 백조가 있더라도, 그 빙판은 녹기 때문이다.

     쉽게 생각해서 물인 지점에 대해서 Queue에 모두 넣어주었다고 생각하고 접근하자.

   - 물인 지점에서 인접한 방향으로 나아갈 때

     인접한 방향이 빙판이라면 : 물의 Next Queue에 push후 진행 & 해당 정점을 물로 바꿔주기.

     이 부분에 대해서만 구현을 해주면 된다.

   

    그렇다면, 위의 과정을 진행했다면 물과, 백조의 NextQueue에는 무슨 값들이 들어가있는지 확인해보자.

   위의 그림은 문제의 예제입력1을 MAP처럼 가져온 것이다. 위의 상태에서 물과 백조의 Next Queue에는 무슨 값들이 들어가

   있는지 확인해보자.

 위의 상태가 Next Queue에 들어간 정점들이다. 물론, 파랑색으로 표시된 백조의 Next Queue에 들어있는 정점들은

 백조의 Next Queue에 들어가있음과 동시에 물의 Next Queue에도 들어가 있을 것이다.

 위의 점들을 다시 현재의 Queue로 옮기고 (Next_Queue -> Queue) Queue에 들어있는 정점들에 대해서

 백조에 대한 BFS(), 물에 대한 BFS()를 다시한번 진행한다면??

 우리가 처음 실행했던 BFS()에서 이미 방문한 정점들은 다시 방문을 해야하는 낭비가 없어질 것이다.

 자연스럽게 탐색하는 횟수도 훨씬 줄어들 것이고, 프로그램의 시간이 훨씬 줄어들 것이다.

 위의 색깔로 표시된 점들은 하루가 지나면 물로 바뀌게 된다. 물로 바뀐 상태를 확인해보자.

 이 상태에서, 위에서 설명한대로 백조에 대한 NextQueue, 물에대한 NextQueue를 만들어서 진행한다면, Visiti배열의 초기화

 없이, 탐색한 지점을 다시 탐색하지 않으면서 탐색 횟수를 최소화 시킬 수 있을 것이다.

[ 소스코드 ]

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 1500
using namespace std;
 
int R, C;
bool Find;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
queue<pair<int, int>> Swan_Q, Swan_NQ, Q, NQ;
pair<int, int> Swan_Pos;
 
void Input()
{
    Find = false;
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] != 'X') Q.push(make_pair(i, j));    
            if (MAP[i][j] == 'L')
            {
                Swan_Pos.first = i;
                Swan_Pos.second = j;
            }
        }
    }
}
 
void Swan_BFS()
{
    while (Swan_Q.empty() == 0 && Find == false)
    {
        int x = Swan_Q.front().first;
        int y = Swan_Q.front().second;
        Swan_Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < R && ny < C)
            {
                if (Visit[nx][ny] == false)
                {
                    if (MAP[nx][ny] == '.')
                    {
                        Visit[nx][ny] = true;
                        Swan_Q.push(make_pair(nx, ny));
                    }
                    else if (MAP[nx][ny] == 'L')
                    {
                        Visit[nx][ny] = true;
                        Find = true;
                        break;
                    }
                    else if (MAP[nx][ny] == 'X')
                    {
                        Visit[nx][ny] = true;
                        Swan_NQ.push(make_pair(nx, ny));
                    }
                }
            }
        }
    }
}
 
void Water_BFS()
{
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < R && ny < C)
            {
                if (MAP[nx][ny] == 'X')
                {
                    MAP[nx][ny] = '.';
                    NQ.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Solution()
{
    int Day = 0;
    Swan_Q.push(make_pair(Swan_Pos.first, Swan_Pos.second));
    Visit[Swan_Pos.first][Swan_Pos.second] = true;
 
    while (Find == false)
    {
        Swan_BFS();
 
        if (Find == false)
        {
            Water_BFS();
            Q = NQ;
            Swan_Q = Swan_NQ;
 
            while (NQ.empty() == 0) NQ.pop();
            while (Swan_NQ.empty() == 0) Swan_NQ.pop();
            Day++;
        }
    }
    cout << Day << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}