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

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

3197번: 백조의 호수

모든 빙판이 물과 닿으면 녹는다고 할때 (닿는다는 기준은 상하좌우로 물이 인접해있을 경우) 백조 두 마리가 만나는데 며칠이 소요되는가를 구하는 문제이다.

 

우선 알아두면 좋은게, 백조가 있는 칸도 물로 취급한다. 즉

1 7 LXX.XXL 같은 입력이 들어오면 정답은 1이다. 설명이 애매해서 추가해줬으면 좋겠는데 (https://www.acmicpc.net/board/view/45802) 추가되지 않는게 좀 아쉽다.

 

우선 R과 C의 크기가 크니까 매 번 모든 점을 넣고 돌려보는 BFS로는 안 된다고 생각했고, 예전에 풀었던 문제처럼 처음에 시작점을 주고, 그 시작점에서 확장하는 형태로 풀어야겠다고 생각했다.

또한 백조가 만날 수 있는지 먼저 확인 후(1) 날짜의 경과를 구해야하기 때문에(2) 백조가 만났는지 확인하는 BFS를 먼저 구현하고, 큐에 들어간 원소의 개수만큼만 while문을 돌려서 딱 하루치만 BFS를 하도록 구현했다.

 

결론적으로 내가 생각한 방법은 다음과 같다.

1. 백조가 만날 수 있는지 확인하는 BFS - 1번 백조에서 시작해서 X와 맞닿아있는 지점을 임시 큐 sub2에 추가하고, 

백조가 물 공간으로 갔을때는 큐 q에 추가해서 q가 빌때까지 수행. 이 sub2는 백조 확인용 BFS를 하기 전에 큐 q로 이동한다. 만약 큐 q에서 꺼낸 원소가 2번 백조의 위치와 같다면 종료한다.

2. 빙판을 녹이는 BFS - 처음에 board[i][j]에 넣을때 물이나 백조 공간이라면 모두 sub에 추가하고, 이 sub의 개수만큼만 while문을 돌리면서 BFS를 한다. 만약 BFS를 하면서 X를 만난 경우 Copy[nx][ny]를 true로 변경하고(visited 역할) board[nx][ny]를 '.'으로 변경한다. 이후 sub 큐에 push한다.

3. 1,2번을 계속 반복한다. 

 

처음에는 2번 과정에서 board[nx][ny]를 .으로 변경하지 않고 한번에 처리하기 위해 for (int i=0;i<r; i++) for (int j=0; j<c; j++)에서 copy[i][j]가 true면 board[i][j]를 '.'으로 변경하고 copy를 모두 false로 처리했는데, 이도 통과는 되지만 처리하지 않은 코드와 시간 차이가 꽤 많이 나서(140ms와 500ms) 계속 생각해보니까 2중 for문이 필요가 없었다.

 

어차피 2번 BFS를 수행할때 sub 큐에 {nx,ny}가 push될거고, 한번 간 지점은 이미 물로 바뀌었으니까 갈 필요가 없어서 Copy[i][j]를 false로 만들면 중복해서 방문하기 때문이다.

 

 

    #include <iostream>
    #include <queue>
    using namespace std;
    #define MAX 1502
    #define X first
    #define Y second
    int dx[4] = { 1,0,-1,0 };
    int dy[4] = { 0,1,0,-1 };
    queue <pair<int, int>> q, sub, sub2;
    char board[MAX][MAX];
    bool vis[MAX][MAX],Copy[MAX][MAX];
    int r, c;
    pair <int, int> L1, L2;
    void input()
    {
        bool flag = false;
        cin >> r >> c;
        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                cin >> board[i][j];
                if (board[i][j] == 'L')
                {
                    if (!flag)
                    {
                        L1 = { i,j }; // 백조 1번
                        q.push({ i,j }); // 큐의 시작위치
                        vis[i][j] = true;
                        flag = true;
                    }
                    else
                        L2 = { i,j };
                }
                if (board[i][j] != 'X')
                {
                    sub.push({ i,j }); // sub 큐의 시작 원소들
                }
            }
        }
    }
    int solve()
    {
        int day = 0;
 
        while (true)
        {
            while (!sub2.empty()) // 빙판과 맞닿은 점들
            {
                q.push(sub2.front()); sub2.pop();
            }
            while (!q.empty())
            {
                auto cur = q.front(); q.pop();
                if (cur.X == L2.X && cur.Y == L2.Y)
                    return day;
                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
 
                    if (nx < 0 || ny < 0 || nx >= r || ny >= c || vis[nx][ny]) continue;
                    if (board[nx][ny] == 'X') // 빙판과 맞닿아있다면 sub2에 push하고 이 큐가 끝나고 다음 외부
                                                //while이 돌때 q로 이동
                    {
                        sub2.push({ cur.X,cur.Y });
                        continue;
                    }
                    vis[nx][ny] = true;
                    q.push({ nx,ny });
                }
            }
 
                int t = sub.size();
                while (t--) // sub 큐의 개수만큼만 반복하기
                {
                    auto cur = sub.front(); sub.pop();
                    for (int dir = 0; dir < 4; dir++)
                    {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
 
                        if (nx < 0 || ny < 0 || nx >= r || ny >= c || Copy[nx][ny]) continue;
 
                        if (board[nx][ny] == 'X') // 빙판이면 녹이고 Copy를 true로 변경 - 방문함
                        {
                            Copy[nx][ny] = true;
                            sub.push({ nx,ny });
                            board[nx][ny] = '.';
                        }
                    }
                }
 
                day++;
            
 
            /*for (int i = 0; i < r; i++) // 이 문장이 없어도 정답처리되며, 오히려 없어야함
            {
                for (int j = 0; j < c; j++)
                {
                    if (Copy[i][j])
                    {
                        board[i][j] = '.';
                        Copy[i][j] = false;
                    }
                }
            }*/
        
        }
    }
    int main()
    {
        cin.tie(0); ios::sync_with_stdio(0);
        input(); cout << solve();
    }