[BOJ 3197] 백조의 호수

#문제

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

#풀이

문제를 보면 크게 두가지를 확인해야 합니다.

우선 일마다 얼음이 어디가 녹는지 확인을 해야하고, 그 맵에서 언제 백조들이 만날 수 있는가를 확인하면 됩니다.

처음으로 제가 생각해본 방법은 가장 단순하게 하루하루 물과 근접한 얼음들을 녹게하고, 

백조들이 만나는지 확인하는 알고리즘을 세웠습니다.

얼음을 녹이는 것과 백조들이 만날 수 있는지 확인하는것 모두 BFS를 사용하여 풀었었습니다.

하지만 이게 왠걸...최대 크기를 완전 고려하지 않았습니다...

R과 C가 모두 최대 1500...

만약 위와 같은 방법으로 했을 경우, 물인 곳을 넣고 퍼지게 하는 것만 O(R * C) 걸리게 되고, 

그 안에서 백조들이 만나는지 확인하는데 또 다시 O(R*C)만큼이 걸리게 되므로 와우... 

말하지 않아도 시간 초과가 날 수 있다는 것을 알게 됩니다.

어떻게 조금더 줄일 수 있을까요?

미리 얼음을 녹이는 일 수를 알고 있으면 되지 않을까요?

즉, 1일에 녹일 수 있는 공간은 1, 2일차에 녹일 수 있는 얼음들은 2... 이런식으로 늘려 가면서 다른 곳에 저장을 하는 것입니다.

입력으로 주어진 맵의 경우

0	0	0	1	2	3	3	2	1	0	0	1	1	0	1	2	2
0	0	0	0	1	2	3	2	2	1	1	2	1	0	1	1	1
0	0	0	1	2	3	2	1	1	2	2	3	2	1	1	0	0
0	0	1	2	3	2	1	0	0	1	2	3	3	2	1	0	0
0	1	2	3	3	2	1	0	0	1	2	3	3	2	1	0	0
1	1	2	2	3	2	1	0	0	0	1	2	2	1	0	0	0
0	0	1	1	2	2	1	0	0	0	1	2	1	0	0	0	0
0	0	0	0	1	2	2	1	1	0	1	2	1	0	0	0	0

식으로 나오게 됩니다. 참고하세요!

여기서 1일 차에 움직일 수 있는 곳~ 2일차에 움직일 수 있는 곳~ 이렇게 백조들이 만날 수 있는 가를 찾는다면 

최대 1499일까지 기다려야 하므로 시간 복잡도는 O(1499*R*C) 가 됩니다.

( R*C = 백조들이 만나는지 확인하는 시간 )

역시나.. 엄청난 시간이 걸리게 되는 것 같습니다.. 여기서도 시간초과가 나게 됩니다.

여기서 생각만 하는데 많은 시간이 걸렸고, 결국에는 검색을 하게 되었습니다... ㅠㅠ...

혹시나 생각이 나지 않는다면 문제 옆에 있는 질문 검색을 눌러보는게 굉장히 도움이 됩니다!(아래 그림 참조!)

검색한 결과! 아..오늘도 자괴감을 얻고 가네요... :( 

머리가 똑똑하신 분들은 금방 찾으셨을 수도 있겠습니다.

바로 "N일때 백조들이 만나지 못한다면, N일 전 날 모두 만날 수 없다" 라는 점입니다.

예를 들어, 얼음이 녹은지 5일이 되어도 백조들이 만나지 못한다면 그 이후의 만날 수 있는 날들 중에서 확인을 하여합니다.

이와 유사하게 적용할 수 있는 알고리즘이 있습니다. 바로 이분법인데요!

이분법을 사용하면 최대 녹는 일을 계속해서 반으로 줄일 수 있으므로 

시간복잡도를 O(Log21499 * 1500 * 1500) 까지 줄일 수 있습니다.

아까 위에서 얼음들이 녹는 시간을 저장 했으니 얼음이 다 녹는 일 수를 찾을 수 있겠죠?

따라서 최대 일과 0일(시작하는 날에도 만날 수 있음!) 사이에서 중간 날의 값을 계속해서 확인해 가면서 

할 필요 없는 날들을 빼버리는 것이 바로 이 문제의 핵심입니다.

코드를 보면서 이해해 봅시다!

#코드

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define MAX 1501
 
using namespace std;
 
//맵
char map[MAX][MAX];
//얼음이 녹는 시간 저장
int meltingDay[MAX][MAX];
//백조들이 만날 수 있는지 확인할 때 사용
bool visit[MAX][MAX];
 
int R,C;
//백조의 위치 저장 1:시작 2:끝
vector<pair<int, int>> swan;
//얼음이 녹는데 걸리는 최대 일
int maxDay = 0;
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
//백조들이 만날 수 있는가를 확인(BFS)
bool checkMeetingSwans(int day){
    //일 수 마다 확인을 해야하므로 확인 할 때마다 초기화
    memset(visit, false, sizeof(visit));
    queue<pair<int, int>> q;
    q.push({swan[0].first, swan[0].second});
    visit[swan[0].first][swan[0].second] = true;
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        if(r == swan[1].first && c == swan[1].second){
            return true;
        }
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(nr < 1 || nr > R || nc < 1 || nc > C) continue;
            if(visit[nr][nc] || meltingDay[nr][nc] > day) continue;
            q.push({nr,nc});
            visit[nr][nc] = true;
        }
    }
    return false;
}
 
//얼음이 녹는 일을 확인(BFS)
void meltingIce(){
    memset(meltingDay, -1, sizeof(meltingDay));
    queue<pair<int, int>> q;
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            if(map[i][j] == '.' || map[i][j] == 'L'){
                q.push({i,j});
                meltingDay[i][j] = 0;
            }
        }
    }
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(nr < 1 || nr > R || nc < 1 || nc > C) continue;
            if(meltingDay[nr][nc] > -1) continue;
            q.push({nr,nc});
            meltingDay[nr][nc] = meltingDay[r][c] + 1;
            if(maxDay < meltingDay[nr][nc]) maxDay = meltingDay[nr][nc];
        }
    }
}
 
int main(){
    cin >> R >> C;
    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++){
            cin >> map[i][j];
            if(map[i][j] == 'L')
                swan.push_back({i,j});
        }
    }
    meltingIce();
    //이분법으로 확인
    //왜냐? 최대 얼음이 있을 수 있는 일 수는 1499일
    //1500 * 1500 맵에서 대각선으로 양 끝만 호수 일 경우 얼음이 녹는 시간만 1499일이 걸린다.
    //백조들이 만날 수 있는 일은 최소 0일 부터 시작해서 최대 얼음이 녹는 일까지
    //백조들이 만날 수 있는지 확인할때 걸리는 시간복잡도는 1500 * 1500
    //따라서 모든 일을 검사 할 때는 1500 * 1500 * 1500 시간이 걸린다.
    //시간 초과!
    
    //만약 N일때 백조들이 만나는가를 확인을 했다고 해보자
    //만나지 못하였다면? 이전에 일 수들은 확인을 안해도 못만난다는 것을 알 수 있다.
    //이 때문에 이분법을 적용 가능
    //이분법의 시간 복잡도는 log2(N)이므로 시간 복잡도는 10 * 1500 * 1500까지 줄 수 있다.
    int start = 0, end = maxDay;
    while(start <= end){
        int mid = (start + end) / 2;
        if(checkMeetingSwans(mid)) end = mid - 1;
        else start = mid + 1;
    }
    cout << start << endl;
    return 0;
}