BOJ 3197(백조의 호수)

📜 문제

문제링크

시간초과 문제로 고민하다 결국 다른분들의 풀이를 참고해서 풀었다. (ㅠㅠ)

---

📖 풀이

1. 공간 복잡도

1) 초기 호수의 상태를 저장할 board 배열
2) bfs를 돌때, 방문여부를 저장할 vis 배열
3) 빙판이 녹는 날짜를 저장할 ice 배열

이렇게 크게 3가지 2차원 배열을 풀이에 사용할 것이고, Max의 경우 이기 때문에 약 6.75*10^6 개의 (char, bool, int) 를 사용하게 된다.
문제에서 제시된 조건은 256Mb로 0.6*10^8 개의 int를 사용할 수 있기 때문에 충분하다.

2. 시간 복잡도

1) 빙판이 모두 녹는데 걸리는 날짜를 저장 O(rc)
2) 이분탐색을 통해서 백조가 만날 수 있는 날짜계산 O(1499*rc)

---

🖥 코드

#include <iostream>
#include <utility>
#include <string>
#include <queue>
using namespace std;

char board[1502][1502];
bool vis[1502][1502];
int ice[1502][1502];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
pair<int,int>swan[2];
int r,c,max_day;

void ice_check(){
    //초기상태에서 물에 해당하는 영역을 queue에 넣어준다.
    queue<pair<int,int>>q;
    for(int y=0; y<r; y++){
        for(int x=0; x<c; x++){
            if(board[y][x]=='.' || board[y][x]=='L'){
                q.push({y,x});
                vis[y][x]=1;
            }
        }
    }
    //bfs를 돌면서, 얼음이 며칠뒤에 물이 얼음이 되는지를 ice배열에 저장
    while(!q.empty()){
        pair<int,int>cur=q.front();
        q.pop();
        for(int dir=0; dir<4; dir++){
            int ny=cur.first+dy[dir];
            int nx=cur.second+dx[dir];
            if(ny<0 || ny>=r || nx<0 || nx>=c)continue;
            if(vis[ny][nx])continue;
            q.push({ny,nx});
            vis[ny][nx]=1;
            ice[ny][nx]=ice[cur.first][cur.second]+1;
            if(ice[ny][nx]>=max_day)max_day=ice[ny][nx];
        }
    }
}

bool bfs(int day){
    //ice_check() or 이전의 bfs()에서 사용한 vis를 초기화
    for(int y=0; y<r; y++)
        for(int x=0; x<c; x++)vis[y][x]=0;
    //백조 한마리가 다른 백조에 다을수 있는지를 검사
    queue<pair<int,int>>q;
    int swan_y=swan[1].first;
    int swan_x=swan[1].second;
    q.push({swan[0].first,swan[0].second});
    vis[swan[0].first][swan[0].second]=1;

    while(!q.empty()){
        pair<int,int>cur=q.front();
        q.pop();
        for(int dir=0; dir<4; dir++){
            int ny=cur.first+dy[dir];
            int nx=cur.second+dx[dir];
            if(ny<0 || ny>=r || nx<0 || nx>=c)continue;
            if(vis[ny][nx] || ice[ny][nx]>day)continue;
            q.push({ny,nx});
            vis[ny][nx]=1;
        }
    }
    if(vis[swan_y][swan_x])return true;
    else return false;
}

int main(void){

    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>r>>c;
    //백조좌표 저장 및 초기 board 상태 저장
    int i=0;
    for(int y=0; y<r; y++){
        string s;
        cin>>s;
        for(int x=0; x<c; x++){
            board[y][x]=s[x];
            if(board[y][x]=='L'){
                swan[i].first=y;
                swan[i++].second=x;
            }
        }
    }
    //물이 녹는걸 bfs한번 O(N)에 찾고, 이분탐색을 통해서 정답을 찾는다.
    ice_check();
    int start=1, end=max_day;
    while(start<=end){
        int mid=(start+end)/2;
        if(bfs(mid))end=mid-1;
        else start=mid+1;
    }
    cout<<start;

    return 0;
}

---

🔨 피드백

처음 문제를 봤을때, board의 크기를 고려하지 않고

• BFS를 통해서 물과 인접한 빙판을 녹임
• BFS를 통해서 한 백조가 다른 백조에 다을 수 있는지를 검사

이 두과정을 백조가 만날때 까지 반복했다. 최악의 경우를 생각해보면 O(2*1500*1500) 를 백조가 만날때 까지 반복하게 된다.

22일을 넘어가게 되면 시간초과가 발생하게 되고, 고려하지 않은 초기화 과정을 추가하면 무조건 시간초과가 나게 된다. 이런 시간초과를 어떻게 피할 수 있을지를 고민하다가 결국 다른분들의 코드를 참고해 힌트를 얻었다.

N번째날 백조가 만나지 못했다면 N-1번 이전에 백조가 만나지 않는다.

그렇다. 처음 BFS를 통해서 빙판이 며칠째에 녹는지를 저장하고 이를 이용해 첫번째 날부터 빙판이 모두 녹는날까지를 기준으로 이분탐색을 적용하면 된다.
최악의 경우 빙판이 모두 녹는날짜는 1499일, 호수는 1500x1500의 크기를 가진다.
O(1499*1500*1500) -> O(10*1500*1500)

이분탐색을 적용하면, 주어진 시간내에 문제를 해결할 수 있음을 알 수 있다.

⌛️ 꼭 다시 풀어봐야겠다!