글 읽기 - 틀린 이유를 모르겠습니다. (정올 채점 데이터는 맞는데 백준에서 틀려요)

vl0612 5년 전 0

음...지난 질문글(https://www.acmicpc.net/board/...)을 통해 오타(...)도 찾고 다시 제출을 했는데 틀렸습니다.

정올 사이트의 채점데이터(https://www.digitalculture.or....) 35개 전부 노가다로 넣어봤는데 다 정답을 출력해서요 ㅠㅠ

정올의 채점 데이터 부실인 걸까요? 아님 백준의 데이터 미스(...?) //틀린 이유 남탓하기 ( 'ㅁ')_{는 아니구...정말 모르겠어요......}

그냥 제 코드가 틀린 거고 노가다 실수이려나요...흑..

반례나 틀린 부분 부탁드립니다 (ㅠ ㅁ ㅠ...)

```
#include<bits/stdc++.h>
using namespace std;
int N,K,x,y,cnt; bool arr[2010][2010];
int m_x[4]={0,1,0,-1},m_y[4]={1,0,-1,0};
struct st{int x,y;}cell;
st par[2010][2010]; int Rank[2010][2010]; int t[2010][2010];
//유니언 파인드 트리
st Find(st a){return a.x==par[a.x][a.y].x&&a.y==par[a.x][a.y].y?a:Find(par[a.x][a.y]);}
void Union(st a,st b){
    st c=Find(a); st d=Find(b);
    if(c.x==d.x && c.y==d.y) return;
    if(Rank[c.x][c.y]>Rank[d.x][d.y]) par[d.x][d.y]=c;
    else if(Rank[c.x][c.y]==Rank[d.x][d.y]) par[d.x][d.y]=c, Rank[c.x][c.y]++;
    else par[c.x][c.y]=d;
}
queue<st> q;
int main(){
    scanf("%d %d",&N,&K); cnt=K;
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) arr[i][j]=true,par[i][j]=(st){0,0};
    for(int i=1;i<=K;i++){scanf("%d %d",&x,&y);arr[x][y]=false; par[x][y]=(st){x,y}; q.push({x,y});}
    //문명이 하나인 경우 0출력
    if(K==1) {printf("0");return 0;}
    //매우 돌며
    while(1){
        //큐에서 하나씩 꺼내며
        cell=q.front(); q.pop();
        //꺼낸 위치와 주변이 서로 다른 문명인지 체크
        for(int j=0;j<=3;j++){
            //주변을 방문한 적이 없고 서로 다른 문명이면
            if((!(par[cell.x+m_x[j]][cell.y+m_y[j]].x==0 && par[cell.x+m_x[j]][cell.y+m_y[j]].y==0))&&(!(Find(par[cell.x+m_x[j]][cell.y+m_y[j]]).x==Find(par[cell.x][cell.y]).x&&Find(par[cell.x+m_x[j]][cell.y+m_y[j]]).y==Find(par[cell.x][cell.y]).y))){
                //합치고
                Union({cell.x+m_x[j],cell.y+m_y[j]},{cell.x,cell.y});
                //다 합쳐서 문명이 하나 남으면 출력하고 리턴
                cnt--; if(cnt==1){printf("%d",max(t[cell.x][cell.y],t[cell.x+m_x[j]][cell.y+m_y[j]])); return 0;}
            }
        }
        //꺼낸 위치의 주변으로 문명 확산
        for(int i=0;i<=3;i++){
            if(arr[cell.x+m_x[i]][cell.y+m_y[i]]==true){
                par[cell.x+m_x[i]][cell.y+m_y[i]]=Find(cell);
                arr[cell.x+m_x[i]][cell.y+m_y[i]]=false;
                q.push({cell.x+m_x[i],cell.y+m_y[i]});
                t[cell.x+m_x[i]][cell.y+m_y[i]]=t[cell.x][cell.y]+1;
            }
        }
    }
}
```

vl0612 5년 전 2

일단 해결..!

cubelover_dev 님께서 반례를 찾아주셨습니다.

2 3

2 2

1 1

2 1

정답:0

출력:1

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

문제

문제

출처

ICPC

틀린 이유를 모르겠습니다. (정올 채점 데이터는 맞는데 백준에서 틀려요)

vl0612 5년 전 0

vl0612 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말