3197-백조의 호수

www.acmicpc.net/problem/3197

3197번: 백조의 호수

본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다.

 

알고리즘 구현시 최적화를 굉장히 많이 신경써야 하는 문제였습니다.

 

알고리즘은 다음과 같습니다.

 

1. 두 백조 중, 한 백조를 고정시키고 나머지 한 백조를 이동시키며 방문할 수 있는 지역을 방문한다. 이 때, 고정된 백조가 있는 지역에 방문하면 현재 일자를 정답으로 출력한다.

2. 호수의 상태를 업데이트 한다.

3. 일자를 업데이트 한다. 

4. 다시 1.의 작업을 수행한다.

 

이 중, 핵심은 1.과 2.로써 해당 작업들을 최적화 하는 것이 이 문제의 핵심이라고 생각이 들었습니다.

 

 먼저, 1.의 작업은 BFS 를 통해 구현할 수 있습니다.

 

1-0. 이동시킬 백조의 위치를 Queue(q_swan) 에 삽입한다.

 

1-1. q_swan 에 저장된 백조가 방문할 수 있는 위치를 Pop 하여 해당 위치를 출발점으로 설정한다. 

 

1-2. 출발점으로 부터 상하좌우로 백조를 이동시키며 방문할 수 있는 지역을 방문한다. 이 때, 고정된 백조가 있는 지역에 방문하면 현재 일자를 정답으로 출력한다. 만약 이동시켰을때 방문할 수 없는 지역(얼음)이라면 그 지역을 다음 일자에 방문할 수 있도록 임시 Queue(temp_q_swan) 에 삽입한다.

 

1-2. 의 작업에서 볼드체로 강조한 부분은 알고리즘의 핵심 부분입니다. 호수의 상태가 업데이트 되고나서 다시 백조를 이동시킬때, 우리는 해당 지점(해당 지점은 물이 근처에 있는 얼음 지역이기 때문에 다음날 녹게 됨)으로 부터 백조를 다시 이동시키면 이전에 방문한 지점들을 재방문할 필요없어지기 때문에 불필요한 연산량을 감소시킬 수 있습니다.

 

1-3. q_swan 이 빌때까지 1-1.~1-3. 을 반복한다.

 

1-4. q_swan 을 temp_q_swan 으로 대체한다.

 

이후 1.의 작업이 수행돼야 할 경우 1-1. 부터 1-4. 의 작업을 수행한다.

 

2. 의 작업 또한 BFS 를 이용하여 구현할 수 있습니다.

 

2-0. 호수에서 얼음이 아닌 지역들을 모두 Queue(q_load) 에 저장한다.

 

2-1. q_load 로 부터 얼음이 아닌 지역을 Pop 하여 해당 위치를 기점으로 상하좌우 지역을 검사한다. 이 때, 주위에 얼음인 지역이 있는 경우 그 지역을 물로 변경하고 이를 임시 Queue(temp_q_load) 에 저장한다.

 

2-2. 의 작업에서 볼드체로 강조한 부분은 알고리즘의 핵심 부분입니다. 얼음인 지역은 상하좌우 위치에 물인 지역(백조가 있는 지역도 포함)이 있어야만 녹을 수 있습니다. 이에따라, 물인 지역을 저장해가며 그 주위에 얼음이 있는지를 검사하고 있다면 얼음을 녹이고, 다음날에는 이전날 녹아서 물이된 지역 주위만 검사하면 됩니다.

 

2-2. q_load 가 빌때까지 2-1을 반복한다.

 

2-3. q_load 를 temp_q_load 로 대체한다.

 

이후 2.의 작업이 수행돼야 할 경우 2-1. 부터 2-3. 의 작업을 수행한다.

 

처음에 구현을 얼음인 지역을 Queue에 저장하고 얼음 주위에 물이 있으면 얼음을 녹이고 아닌 경우 녹지 않은 얼음 지역들만 다음 일자에 재검사하도록 코드를 구현했었는데 이렇게 구현하니 시간초과가 되었습니다. 곰곰히 생각해보니, 두 마리의 백조가 있는 위치를 제외하고 모든 지역이 얼음으로 채워져있는 경우에 얼음인 지역을 Queue 에 저장하여 문제를 푸는 것보다 물인 지역을 Queue 에 저장하고 그 전날에 얼음이 녹은 영역 주위만 다시 검사하는 것이 Queue 의 원소를 순회하는 횟수를 훠어어어얼씬 줄일 수 있겠다는 생각이 들었고 물인 지역을 Queue에 저장하여 풀도록 구현을 수정하니 문제가 해결됐습니다.

 

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("3197.txt", "r", stdin);

    long long R, C; // R:height, C:width
    vector<vector<char>> map;
    vector<vector<bool>> v;

    vector<pair<int, int>> swans; //{x, y}
    queue<pair<int, int>> q_swans; //{x, y}

    queue<pair<int, int>> q_load;

    pair<int, int> dirs[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    cin >> R >> C;

    map = vector<vector<char>>(R, vector<char>(C));
    v = vector<vector<bool>>(R, vector<bool>(C, false));

    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
        {
            cin >> map[r][c];
            if (map[r][c] == 'L')
            {
                swans.push_back({c, r});
                q_load.push({c, r});
            }
            else if (map[r][c] == '.')
                q_load.push({c, r});
        }
    
    
    q_swans.push(swans[0]);
    v[swans[0].second][swans[0].first] = true;

    bool meet = false;
    int day = 0;

    do
    {
        queue<pair<int, int>> temp_q_swans;
        while(!q_swans.empty())
        {
            int x = q_swans.front().first;
            int y = q_swans.front().second;
            q_swans.pop();

            for(pair<int, int> dir:dirs)
            {
                int nx = x + dir.first;
                int ny = y + dir.second;

                if(nx < 0 or nx >= C) continue;
                if(ny < 0 or ny >= R) continue;
                if(v[ny][nx]) continue;

                v[ny][nx] = true;
                if(nx == swans[1].first && ny == swans[1].second) 
                {
                    meet = true;
                    break;
                }
                else if(map[ny][nx]=='X') 
                {
                    temp_q_swans.push({nx, ny});
                }
                else
                {
                    q_swans.push({nx, ny});
                }
            }
            if(meet) break;
        }
        q_swans = temp_q_swans;
        if(meet) break;

        queue<pair<int, int>> temp_q_load;
        while(!q_load.empty())
        {   
            int x = q_load.front().first;
            int y = q_load.front().second;
            q_load.pop();

            bool melted = false;
            for(pair<int, int> dir:dirs)
            {
                int nx = x + dir.first;
                int ny = y + dir.second;

                if(nx < 0 or nx >= C) continue;
                if(ny < 0 or ny >= R) continue;

                if(map[ny][nx] == 'X') 
                {
                    map[ny][nx] = '.';
                    temp_q_load.push({nx, ny});
                }
            }
        }
        q_load = temp_q_load;
        day += 1;
    } while (true);

    cout << day;

    return 0;
}