글 읽기 - 예외케이스가 있는지 알고싶습니다

juhongkim2 7년 전 0

1. B에 도착 할 경우 flag=1로 해주고 B에 도착하지 못할경우엔 flag=0으로 해서

flag==0이면 -1을 출력하고 flag==1이면 저장해둔 부모노드를 역추적해서 경로를 저장하고 출력하도록 만들었습니다.

자꾸 90퍼센트에서 틀렸습니다가 나오길래

2. flag변수를 아예 없애버리고 B에서 부모노드를 역추적 했을때 마지막노드(출발노드)가 A가 아니면 -1을 출력하고

역추적 결과 A에 도착하면 경로를 출력하도록 바꿨더니 패스되네요

분명 시작노드를 A로 하고 BFS를 돌린건데 1번처럼 풀면 틀린결과가 나오는 걸까요?

#include <stdio.h>

int N,K,A,B,map[1010][1010],input[1010][50],route[1010],check[1010],p[1010],queue[1010*2],flag;

int main()
{
	int i,j,l,len,f,r,out,now;

	scanf("%d %d",&N, &K);

	for(i=1;i<=N;i++){
		for(j=0;j<K;j++){
			scanf("%1d",&input[i][j]);
		}
	}

	scanf("%d %d",&A, &B);

	for(i=1;i<=N;i++){
		for(j=i+1;j<=N;j++){
			len=0;
			for(l=0;l<K;l++){
				if(input[i][l]!=input[j][l])
					len++;
			}
			map[i][j]=map[j][i]=len;
		}
	}

	f=r=-1;
	queue[++r]=A;
	p[A]=A;
	check[A]=1;

	len=0;
	while(f!=r){
		out=queue[++f];
		flag=0;

		if(out==B){
			flag=1;
			break;
		}

		for(i=1;i<=N;i++){
			if(map[out][i]==1 && check[i]==0){
				queue[++r]=i;
				p[i]=out;
				check[i]=1;
			}
		}
	}

	now=B;
	len=0;
	if(flag=0)
		printf("-1\n");
	else{
		while(1){
			route[len++]=now;
			if(p[now]==now)
				break;
			now=p[now];
		}

		for(i=len-1;i>=0;i--){
			printf("%d ",route[i]);
		}
		printf("\n");
	}

	return 0;
}

methylene 7년 전 0

56번 째 줄에 if(flag = 0) 는 옮겨쓰다 오타가 난 건가요?

아니라면 그것 때문에 틀린 것이 아닌가 조심스레 추측해 봅니다.

juhongkim2 7년 전 0

B에 도착하지 못할경우 flag=0해서 -1출력하도록짠건데...

저걸 고쳐서 맞았으니 저부분이 문제인거 같기는 한데 저부분 빼면 -1이 출력안되거든요

논리는 맞는거 같은데 틀려서 참 찝찝하네요

methylene 7년 전 1

flag == 0 을 잘못 쓴 것 같다고 말한 건데...

juhongkim2 7년 전 0

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

미치겠네요 지적감사합니다

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

문제

문제

출처

ICPC

예외케이스가 있는지 알고싶습니다

juhongkim2 7년 전 0

methylene 7년 전 0

juhongkim2 7년 전 0

methylene 7년 전 1

juhongkim2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말