글 읽기 - 촌수계산 질문게시판 반례 전부 맞게 나오는데 틀렸다네요

david921 4년 전 0

단 한 경우 n이 3이라고 제시되었는데 숫자가 6을 받는 경우 이런 경우에만 비정상적인 동작이 됬고, 나머지 경우에서는 전부 반례라고 제시된 경우에서 올바른 답을 도출했는데, 뭐가 문제인지 알 수 있을까요? 생각나는 방식으로 풀었지만, 직관적인 코드입니다.

가장 가까운 공통 부모를 찾아 그 거리를 계산합니다.

#include <stdio.h>
#include <stdlib.h>

int parent1[101] = {0, };
int parent2[101] = {0, };

int n, x, y, m, tmp1, tmp2, c1, c2;
int **rel;

void findparent1(int a);
void findparent2(int a);
void finddistance(void);

int main(void){

	scanf("%d", &n);
	scanf("%d %d", &x, &y);
	scanf("%d", &m);
	
	if(x == y){
		printf("-1");
		return 0;
	}
	
	rel = (int**)calloc((n+1), sizeof(int*));
	
	for(int i = 0; i < n + 1; i++){
		rel[i] = (int*)calloc((n+1), sizeof(int));
	}
	
	for(int i = 0; i < m; i++){
		scanf("%d %d", &tmp1, &tmp2);
		rel[tmp1][tmp2] = 1;
	}
	
	findparent1(x);
	findparent2(y);
	
	finddistance();
	
	return 0;
}

void findparent1(int a){
	int tmp = a;
	int ch = 1;
	c1 = 0;
	
	while(ch){
		ch = 0;
		for(int i = 1; i < n + 1; i++){
			if(rel[i][tmp] == 1){
				tmp = i;
				parent1[c1] = i;
				c1++;
				ch = 1;
			}
		}
	}
}
void findparent2(int a){
	int tmp = a;
	int ch = 1;
	c2 = 0;
	
	while(ch){
		ch = 0;
		for(int i = 1; i < n + 1; i++){
			if(rel[i][tmp] == 1){
				tmp = i;
				parent2[c2] = i;
				c2++;
				ch = 1;
			}
		}
	}
}
void finddistance(void){
	int check = 0;
	int distance;
	for(int i = 0; i < c1; i++){
		for(int j = 0; j < c2; j++){
			if(parent1[i] == parent2[j]){
				if(check == 0){
					distance = i + j + 2;
				}
				else{
					if(distance > i + j + 2){
						distance = i + j + 2;
					}
				}
				check = 1;
				
			}
		}
	}
	if(check){
		printf("%d", distance);
	}
	else{
		printf("-1");
	}
}

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

문제

문제

출처

ICPC

촌수계산 질문게시판 반례 전부 맞게 나오는데 틀렸다네요

david921 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말