글 읽기 - 단자번호 dfs 반례좀 찾아주세요

ljh971201 5년 전 0

질문게시판에서 반례를 찾아봤는데 25* 25 0101010... 반복되는 예시도 통과되고 아무리 생각해봐도 반례를 못찾겠네요 ㅠㅠ 반례좀 찾아주세요

#include<stdio.h>
int n,map[27][27]={0},a[27],b[27],cnt,num[400];
void que(int x, int y) //큐에 저장
{
	map[x][y]=-1; // 중복방문 방지
	a[cnt]=x;
	b[cnt]=y;
	cnt++;
}

void dfs(int x ,int y)
{
	int pos=0,p,q;
	que(x,y);
	while(pos < cnt) // 큐가 비게되면 dfs 종료
	{
		p=a[pos];
		q=b[pos];
		
		if(p > 0 && map[p-1][q] == 1)
		{
			que(p-1,q);
		}
		if(p < n-1 && map[p+1][q] == 1)
		{
			que(p+1,q);
		}
		if(q > 0 && map[p][q-1] == 1)
		{
			que(p,q-1);
		}
		if(q < n-1 && map[p][q+1] == 1)
		{
			que(p,q+1);
		}

		pos++;
	}
}

int main(void)
{
	char t[30];
	int i,j,k=0,q;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%s",t);
		for(j=0;j<n;j++)
		{
			if(t[j] == '1')
			{
				map[i][j]=1;
			}
		}

	}

	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(map[i][j] ==1)
			{
				cnt=0;
				dfs(i,j);
				num[k]=cnt; //  큐에 들어간 숫자 개수를 저장해준다
				k++; // dfs를 돌린횟수
			}
		}
	}
	for(i=0;i<k-1;i++) // 정렬
	{
		for(j=0;j<k-1;j++)
		{
			if(num[j]>num[j+1])
			{
				q=num[j];
				num[j]=num[j+1];
				num[j+1]=q;
			}
		}
	}
	printf("%d\n",k);
	
	for(i=0;i<k;i++)
	{
		printf("%d\n",num[i]);
	}
}

Green55 5년 전 1

a, b의 크기가 최소 25*25는 되야하지 않을까요?

N=25이고 전부 1로 채워진 케이스가 제대로 돌아가지 않을 것 같습니다.

ljh971201 5년 전 0

ㅠㅠ 덕분에 해결했습니다 감사합니다!

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

문제

문제

출처

ICPC

단자번호 dfs 반례좀 찾아주세요

ljh971201 5년 전 0

Green55 5년 전 1

ljh971201 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말