[백준] 14868 문명

bfs + union_find를 배우고 풀면서 이 문제를 풀어봤다

 

각 칸들을 하나의 집합이라보고 문명을 bfs를 통해 넓혀가면서 4방향으로 합쳐주면 된다

합치면서 0이였던 칸은 1로 바꿔주며 큐에 넣어준다

문명이 커지다가 문명끼리 인접해도 합쳐지기 때문에 한번씩 더 봐줬다

 

근데 문제는 마지막에 다 합쳐졌는지 확인하는 과정에서

완탐을 버리지못하고 하나하나 다 확인해줬다~~! 

시간이 덕분에 쭉~쭉 증가했다

 

내일 이것좀 수정해봐야겠다

추가로 이분탐색+bfs를 통해서도 많이 해결하던데

한번 공부해봐야겠다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n,k;
int map[2020][2020];
int p[2002*2002];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
pair<int,int> vt[100010];
 
int find(int x){
    if(p[x]==x) return x;
    return p[x] = find(p[x]);
}
 
void merge(int x,int y){
    x = find(x);
    y = find(y);
    if(x==y) return;
    p[x]=y;
}
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<n);
}
int getN(int x,int y){
    return (x*n+y);
}
int main(){
    //freopen("input.txt","r",stdin);
    for(int i=0;i<2000*2000+1;i++) p[i]=i;
    queue<pair<int,int>> q;
    scanf(" %d %d",&n,&k);
    for(int i=0;i<k;i++){
        int x,y; scanf(" %d %d",&x,&y);
        map[x-1][y-1]=1;
        vt[i] = {x-1,y-1};
        q.push(vt[i]);
    }
    for(int i=0;i<k;i++){
        int x = vt[i].first;
        int y = vt[i].second;
        for(int j=0;j<4;j++){
            int nx = x+dx[j];
            int ny = y+dy[j];
            if(inner(nx,ny) && map[nx][ny]){
                if(find(getN(x,y)) != find(getN(nx,ny))) 
                    merge(find(getN(x,y)),find(getN(nx,ny)));
            }
        }
    }
    bool check=true;
        for(int i=0;i<k-1;i++){
            if(find(getN(vt[i].first,vt[i].second)) != find(getN(vt[i+1].first,vt[i+1].second))) {
                check=false;
            }
        }
        if(check){
            printf("%d\n",0); return 0;
        }
    int ans=1;
    while(int s = q.size()){
        while(s--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(!inner(nx,ny)) continue;
                if(find(getN(x,y)) == find(getN(nx,ny))) continue;
                if(map[nx][ny]==0) q.push({nx,ny});
                map[nx][ny]=1;
                merge(find(getN(x,y)),find(getN(nx,ny)));
                for(int t=0;t<4;t++){
                    int nnx = nx+dx[t];
                    int nny = ny+dy[t];
                    if(inner(nnx,nny) && map[nnx][nny]==1 && map[nx][ny]==1) 
merge(find(getN(nx,ny)),find(getN(nnx,nny)));
                }
            }
        }
        bool check=true;
        for(int i=0;i<k-1;i++){
            if(find(getN(vt[i].first,vt[i].second)) != find(getN(vt[i+1].first,vt[i+1].second))) {
                check=false; break;
            }
        }
        if(check){
            printf("%d\n",ans); return 0;
        }
        ans+=1;
    }
}

 

확인하는 방법을 완탐말고 다른방법으로 찾았다! ries님의 블로그를 참고했다!

유니온파인드에 집합의 수를 추가로 저장했다

그래서 문명의 총합과 첫번째문명의 집합의 수가 같아지면 끝난다!

 

짧아지긴했지만 아직 좀 느리기 때문에 bfs를 좀 골라서 돌아야할것같다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n,k,total;
int map[2020][2020];
int p[2002*2002];
int cnt[2002*2002];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
pair<int,int> vt[100010];
 
int find(int x){
    if(p[x]==x) return x;
    return p[x] = find(p[x]);
}
 
void merge(int x,int y){
    x = find(x);
    y = find(y);
    if(x==y) return;
    p[max(x,y)] = min(x,y);
    cnt[min(x,y)] += cnt[max(x,y)];
}
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<n);
}
int getN(int x,int y){
    return (x*n+y);
}
int main(){
    for(int i=0;i<2000*2000+1;i++) p[i]=i,cnt[i]=1;
    queue<pair<int,int>> q;
    scanf(" %d %d",&n,&k);
    for(int i=0;i<k;i++){
        int x,y; scanf(" %d %d",&x,&y);
        map[x-1][y-1]=1;
        vt[i] = {x-1,y-1};
        q.push(vt[i]);
    }
    sort(vt,vt+k);
    for(int i=0;i<k;i++){
        int x = vt[i].first;
        int y = vt[i].second;
        for(int j=0;j<4;j++){
            int nx = x+dx[j];
            int ny = y+dy[j];
            if(inner(nx,ny) && map[nx][ny]){
                if(find(getN(x,y)) != find(getN(nx,ny))) 
                    merge(find(getN(x,y)),find(getN(nx,ny)));
            }
        }
    }
    if(k==cnt[find(getN(vt[0].first,vt[0].second))]){
        puts("0"); return 0;
    }
    total=k;
    int ans=1;
    while(int s = q.size()){
        while(s--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(!inner(nx,ny)) continue;
                if(find(getN(x,y)) == find(getN(nx,ny))) continue;
                if(map[nx][ny]==0) {
                    q.push({nx,ny});
                    total+=1;
                }
                map[nx][ny]=1;
                merge(find(getN(x,y)),find(getN(nx,ny)));
                for(int t=0;t<4;t++){
                    int nnx = nx+dx[t];
                    int nny = ny+dy[t];
                    if(inner(nnx,nny) && map[nnx][nny]==1 && map[nx][ny]==1) 
merge(find(getN(nx,ny)),find(getN(nnx,nny)));
                }
            }
        }
    if(total==cnt[find(getN(vt[0].first,vt[0].second))]){
        printf("%d\n",ans); return 0;
    }
        ans+=1;
    }
}