글 읽기 - IDE상에서 예시는 다 동작하는데 제출하면 왜 틀렸다고 뜰까요??

jaejin_me 4년 전 0

입력 다받고 1번 노드부터 자식을 찾아가게 재귀함수로 구현했는데

제출하면 1%도 못올라가고 틀렸습니다 뜹니다 어느 부분이 잘못됐을까요?

#include <stdio.h>
#include <string.h>

using namespace std;

class BTreeNode {
public:
	int parent;
	int link[3]; // 2진트리에서 부모 포함 최대 3개가 연결됨
};

void find_root(int parent,int child);

BTreeNode bt[100001]; // 0번은 사용하지 않음

int main(void) {
	memset(bt, 0, sizeof bt);
	int t;
	int n1, n2;

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	scanf("%d\n", &t);
	bt[1].parent = 1;
	for (int i = 0; i < t-1; i++) {

			scanf("%d %d\n", &n1, &n2); // 입력값을 받아 두 노드의 link배열에 연결된 노드의 번호를 넣어줌

			if (bt[n1].link[0] == 0) // 첫번째 노드를 기준으로 두번째 값을 link배열에
				bt[n1].link[0] = n2;
			else if (bt[n1].link[1] == 0)
				bt[n1].link[1] = n2;
			else
				bt[n1].link[2] = n2;

			
			if (bt[n2].link[0] == 0) // 두번째 노드를 기준으로 첫번째 값을 link배열에
				bt[n2].link[0] = n1;
			else if (bt[n2].link[1] == 0)
				bt[n2].link[1] = n1;
			else
				bt[n2].link[2] = n1;

	}

	for (int i = 0; i <3 ; i++) // 1번 노드에 연결된 값에서 find_root를 적용
	{
		if(bt[1].link[i] != 0)
			find_root(1, bt[1].link[i]);
	}

	for (int i = 0; i < t -1; i++) // 2번 노드부터 부모번호 출력
	{
		printf("%d\n", bt[i+2].parent);
	}
	
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
#endif

	return 0;
	
}

void find_root(int parent,int child) {
	bt[child].parent = parent; // child의 부모값을 설정
	for (int i = 0; i<3;i++){
		if(bt[child].link[i] != 0 && bt[bt[child].link[i]].parent == 0) // 링크가 존재하고 링크의 부모값이 0이면
			find_root(child, bt[child].link[i]);
	}
}

chogahui05 4년 전 0

예시가 단순하니까 그런 거겠죠.. 조금만 비틀어 보세요..

트리가 2진 트리라는 조건이 어디에 있나요?

게다가 순서만 비틀고 바꾸어도

의도한 답과 다른 답이 출력되네요.

jaejin_me 4년 전 0

정확히 어느부분이 틀렸는지 말씀해 주실수 있으신가요?

이전에 2진 트리로 다르게 풀어도 1%에서 끝나지는 않았거든요

그리고 예시의 경우에 순서를 바꿔도 답은 잘 나오는데요?

chogahui05 4년 전 0

차분하게 잘 생각해 보세요.

반례가 있으니까 틀렸다고 뜨지 않았을까요?

예시에 나온 인풋 조차도 순서도 랜덤하게 바꾸니까.

(한 줄 당 숫자가 2개 나오잖아요. 그 순서조차도 무자비하게 바꿔버린 경우에)

아예 잘못된 답이 출력되는데요.. 제가 반례를 알려드릴 수도 있어요..

그런데 그건 내 공부만 되는 거지. jaemin님의 공부는 안 되는 거잖아요.

쉬운 문제부터 차근 차근 혼자서 찾는 연습을 해 보세요.

어떻게 풀 지도 조금 고민해 보세요.

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

문제

문제

출처

ICPC

IDE상에서 예시는 다 동작하는데 제출하면 왜 틀렸다고 뜰까요??

jaejin_me 4년 전 0

chogahui05 4년 전 0

jaejin_me 4년 전 0

chogahui05 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말