글 읽기 - 문명 반례 질문! 못찾겠습니다...

dahyun1226 4년 전 0

질문게시판에 있는 모든 반례를 넣어보았지만, 그곳엔 오직 성공뿐이었습니다.

도대체 어떤 반례가 있을까요?

맨처음에 그냥 태초의 문명들을 한번씩 다 bfs시켰습니다. 그게 편한 것 같아서...

제발 부탁드립니다..

// #백준온라인저지 #14868번문명 #20200130
// #알고리즘 #프로그래밍
#include <iostream>
#include <queue>
#include <vector>
#define mp make_pair
using namespace std;
/*
설계를 잘해야한다. 문제도 잘 읽어야 한다. 반성하자.
bfs와 유니온파인드를 이용해야한다는 것은 당연하지만, 포인트가 두가지 있다.
맨처음에 합쳐지는 문명은 하나의 문명이 된다는 것.
합쳐진다는게 선이 만나기만 해도 된다는 것. 
난 처음에 이 두 가지 포인트를 다 놓쳤다.
k가 10만이니까 맨처음에 합쳐지는것 정도는 따로 계산해도 크게 상관없을 것 같다. 
4*10만 40만이고 원래 2000*2000*4하면 대략 1600만이니까.
*/
struct civil
{
int year=0;
int parentx=0,parenty=0;
bool firstcivil=0;//최초의 문명인지 유무	
civil(){}
civil(int y,int py,int px, bool first_civil): year(y),parenty(py),parentx(px),firstcivil(first_civil){}//생성자
};
int k,n;
vector<vector<civil>> civils(2001,vector<civil>(2001,civil()));//이게 보드.

pair<int,int> find(int y,int x)//부모를 반환하는 파인드 함수.
{
if(civils[y][x].parentx==x&&civils[y][x].parenty==y)return mp(civils[y][x].parenty,civils[y][x].parentx);
else {
pair<int,int>pcivil=find(civils[y][x].parenty,civils[y][x].parentx);
civils[y][x].parenty=pcivil.first;
civils[y][x].parentx=pcivil.second;
return mp(civils[y][x].parenty,civils[y][x].parentx);
}
}

bool uni(int sony,int sonx,int parenty,int parentx)//성공시 1 반환. 원래 같았으면 0 반환.
{
pair<int,int>son=find(sony,sonx);
if(son.first==0){son.first=sony;son.second=sonx;}// 0일때 부모가 0이 되어있으므로 조심.
pair<int,int>pr=find(parenty,parentx);
if(son.first==pr.first&&son.second==pr.second)return 0;
else
{
civils[son.first][son.second].parenty=pr.first;
civils[son.first][son.second].parentx=pr.second;
return 1;}//부모를 바꿔버린다는 것이 중요
}

int main ()
{
queue<pair<pair<int,int>,int>> q;//y,x,year를 나타낸다.
cin>>n>>k;
for(int i=0;i<k;i++)
{int y,x;cin>>y>>x;
civils[y][x]=civil(0,y,x,1);
q.push(mp(mp(y,x),0));
}
//입력완료.
while(!q.empty())//bfs로 탐색
{
int nowy=q.front().first.first;
 int nowx=q.front().first.second;
 int nowyear=q.front().second;
 q.pop();
int is[4]={1,-1,0,0};//4가지경우
int js[4]={0,0,-1,1};
for(int level=0;level<4;level++)
{int i=is[level];
 int j=js[level];
if(nowy+i>0&&nowx+j>0&&nowy+i<=n&&nowx+j<=n)//보드 안에 있어야지.
 {
	int nexty=nowy+i;
	int nextx=nowx+j;
	if(civils[nowy][nowx].firstcivil==1)
	{if(civils[nexty][nextx].parentx>0)
	{
	if(uni(nexty,nextx,nowy,nowx)){k--;}
	if(k==1){cout<<0; return 0;}
	}}//맨 처음에 최초의 문명 한 바퀴 그냥 돌리기. 그래봐야 10만*4
	else
	{
	if(civils[nexty][nextx].parentx==0)
	{
	uni(nexty,nextx,nowy,nowx);
	 q.push(mp(mp(nexty,nextx),nowyear+1));
	 civils[nexty][nextx].year=nowyear+1;}//빈공간인경우
	
	else{
		if(uni(nexty,nextx,nowy,nowx))k--;//문명이 합쳐진다면 k-
		if(k==1){cout<<civils[nexty][nextx].year;return 0;}
	}
	}
 }
 
if(civils[nowy][nowx].firstcivil==1&&level==3){q.push(mp(mp(nowy,nowx),0));civils[nowy][nowx].firstcivil=0;}//첫번째가 끝났다면 다시 넣어줘야지 
} 
}

}

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

문제

문제

출처

ICPC

문명 반례 질문! 못찾겠습니다...

dahyun1226 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말