[ BOJ 백준 3197번 - 백조의 호수 ] 해설 및 코드

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

 

목적

호수의 얼음이 녹아 두 마리의 백조가 만나게 되는 순간을 구하자.

 

접근법

1. Disjoint-set을 이용해서 얼음에 의해 분리된 지역을, 시간이 흘러 얼음이 녹으면 하나로 합쳐준다.

 

2. 얼음을 녹이는 과정을 BFS로 진행하면서 두 마리의 백조가 같은 집합에 속해있는지 검사한다.

 

3. 다른 방법으로는 BFS를 두단계로 진행하는 것이 있다. 한 가지는 얼음을 녹이는 것이고, 다른 한 가지는 백조를 퍼뜨리는 것이다.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;i++)
#define t(i,j) (C*i+j)
using namespace std;
 
int R,C,p[2250000],di[]={0,0,1,-1},dj[]={1,-1,0,0};
char lake[1500][1501];
struct pos{int i,j;};
queue<pos> q;
vector<int> swan;
 
int find(int x){
    return p[x]<0?x:p[x]=find(p[x]);
}
 
bool isSafe(int i,int j){
    return 0<=i&&i<R&&0<=j&&j<C;
}
 
void melt(int i,int j){
    lake[i][j]='.';
    q.push({i,j});
    int x=find(t(i,j)),y;
    f(d,0,4){
        int ni=i+di[d],nj=j+dj[d];
        if(isSafe(ni,nj)&&lake[ni][nj]=='.'){
            y=find(t(ni,nj));
            if(x!=y)p[y]=x;
        }
    }
}
 
int sol(){
    int ans=0;
    while(!q.empty()){
        if(find(swan[0])==find(swan[1]))return ans;
        int len=q.size();
        f(k,0,len){
            int i=q.front().i,j=q.front().j;q.pop();
            f(d,0,4){
                int ni=i+di[d],nj=j+dj[d];
                if(isSafe(ni,nj)&&lake[ni][nj]=='X')melt(ni,nj);
            }
        }
        ++ans;
    }
    return -1;
}
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    memset(p,-1,sizeof(p));
    cin>>R>>C;
    f(i,0,R){
        cin>>lake[i];
        f(j,0,C)if(lake[i][j]!='X'){
            if(lake[i][j]=='L')swan.push_back(t(i,j));
            melt(i,j);
        }
    }
    cout<<sol();
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.