글 읽기 - 문명 WA 나는데 반례를 못찾겠습니다.

ryute 6년 전 0

Union-Find 자료구조를 사용해 보았습니다.

문명의 발상지, 문명, 미개지를 따로 분리해서 merge 연산으로 구현해 보았는데 WA 판정을 받네요.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int check[2005][2005]; //문명의 발상지면 2, 문명이면 1, 문명이 아니라면 0
pair<int,int> parent[2005][2005]; //어떤 노드의 발상지 정점
int ra[2005][2005]={};

typedef struct DisJointSet //상호 배타적 집합 
{
    int unioned=0;
    DisJointSet(int n)
    {
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++)
                parent[i][j]=make_pair(i,j);
    }
    pair<int,int> fi(pair<int,int> pos)
    {
        int x=pos.first;
        int y=pos.second;
        if(parent[x][y]==make_pair(x,y))
            return make_pair(x,y);
        else return parent[x][y]=fi(parent[x][y]);
    }
    void un(pair<int,int> a, pair<int,int> b)
    {
        a=fi(a);
        b=fi(b);
        int ax=a.first,ay=a.second;
        int bx=b.first,by=b.second;
        if(a==b) return;
        if(ra[ax][ay]<ra[bx][by])
        {
            swap(ax,bx);
            swap(ay,by);
        }
        parent[bx][by]=make_pair(ax,ay);
        if(ra[ax][ay]==ra[bx][by])
            ra[ax][ay]++;
        if(check[ax][ay]==2 && check[bx][by]==2) //만약 합치는 두 트리의 루트가 둘다 문명의 발상이면
            unioned++; //합쳐진 횟수 증가 
            //printf("(%d,%d) & (%d,%d) so Now it is %d\n",ax,ay,bx,by,++unioned);
    }

}DisJointSet;

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    DisJointSet s(n);
    queue<pair<pair<int,int>, int> > Q;
    for(int i=0;i<m;i++)
    {
        int t1,t2;
        scanf("%d %d",&t1,&t2);
        check[t1][t2]=2;
        Q.push(make_pair(make_pair(t1,t2),0));
        for(int j=0;j<4;j++)
            if(check[t1+d[j][0]][t2+d[j][1]]==1)
                s.un(make_pair(t1,t2),make_pair(t1+d[j][0],t2+d[j][1])); //인접해 있으면 합쳐봄 
    }
    if(s.unioned==(n-1))
        printf("0");
    while(!Q.empty())
    {
        int t1=Q.front().first.first;
        int t2=Q.front().first.second;
        int year=Q.front().second;
        Q.pop();
        for(int j=0;j<4;j++) //상하좌우 순회 
        {
            int nt1=t1+d[j][0],nt2=t2+d[j][1];
            s.un(make_pair(t1,t2),make_pair(nt1,nt2)); //일단 융합 
            if(check[nt1][nt2]==0)
            {
                if(nt1<=0 || nt2>n) continue;
                if(nt1<=0 || nt2>n) continue;
                for(int k=0;k<4;k++) //만약에 성공적으로 융합 되었으면
                    if(check[s.fi(make_pair(nt1+d[k][0],nt2+d[k][1])).first][s.fi(make_pair(nt1+d[k][0],nt2+d[k][1])).second]==2) //상하좌우에 문명이 있나 확인하고 
                        s.un(make_pair(nt1,nt2),make_pair(nt1+d[k][0],nt2+d[k][1])); //만약에 있으면 융합 
                //printf("(%d, %d) in Queue\n",nt1,nt2);
                Q.push(make_pair(make_pair(nt1,nt2),year+1));
                check[nt1][nt2]=1;
            }
        }
        //printf("%d %d %d %d\n",t1,t2,year,s.unioned);
        if(s.unioned==(m-1))
        {
            printf("%d",year+1);
            return 0;
        }
    }
    return -1;
}

yclock 6년 전 1

처음에 모두 하나의 문명을 이룰 경우 올바르지 못한 결과를 출력합니다.

반례 데이터입니다.

Input:
2 2
1 1
1 2

Correct Output:
0

Your Output:
1

yclock 6년 전 1

68번째 줄의 if문이 잘못된 것 같습니다.

n-1이 아니라 m-1 같습니다.

ryute 6년 전 1

아... 오타였네요...

처음에 코너케이스 처리해 놓고 다 됐다고 생각한게 문제였네요. 실제로 넣어봤어야 했는데... 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문명 WA 나는데 반례를 못찾겠습니다.

ryute 6년 전 0

yclock 6년 전 1

yclock 6년 전 1

ryute 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말