글 읽기 - 트리 문제 질문입니다.

csh519 6년 전 0

여러 테스트케이스 해봤는데 틀린부분을 모르겠네요 ㅠㅠ

t[] = 부모노드를 가리킵니다.

num[] = 해당노드가 가지고 있는 자식의 수 입니다.

a = 지워지는 노드입니다.

r= 루트 노드의 인덱스입니다.

노드를 입력받은 다음 지워지는 노드를 입력받고,

지워지는 노드가 가리키는 부모노드의 num[] 값을 1 감소시켜줍니다.(자식이 아니므로 이젠)

그리고 자식이 없는 즉 num[] 값이 0인 노드들만 solve()를 돌립니다.

부모를 찾아 DFS를 진행하게 되고, r(루트 노드) 혹은 본인이 루트노드 일때 1을 반환하고.

a(지우는 노드)인 경우에는 0을 반환합니다.

로직상 틀린부분이 없는 것 같아 질문드립니다.

#include <iostream>
#include <string>
#include <cstdio>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <functional>
#include <list>
#include <vector>
#include <queue>
#include <stack>

#define INF 987654321

using namespace std;

int n, t[51], num[51], a, r, ans;

int solve(int d)
{
	if (t[d] == a)
		return 0;
	else if (t[d] == r || t[d] == -1)
		return 1;
	else
		solve(t[d]);
}

int main(void)
{
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a);
		if (a == -1)
			r = i - 1;
		t[i] = a;
		num[a]++;
	}

	scanf("%d", &a);

	num[t[a]]--;

	for (int i = 0; i < n; i++)
		if (num[i] == 0 && i != a)
			ans += solve(i);

	cout << ans;

	return 0;
}

pichulia 6년 전 1

r값이 무진장 이상하네요...

그리고 루트를 지운 경우 배열의 음수인덱스에 접근하게 됩니다.

csh519 6년 전 0

음 그렇군요..

지우는 노드가 루트인 경우는 아래와 같이 처리해줘 봤습니다.

그래도 오답이더라구요.

r 값을 저렇게 두면 안되는 건가요?

int main(void)
{
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a);
		if (a == -1)
			r = i - 1;
		t[i] = a;
		num[a]++;
	}

	scanf("%d", &a);

	if (a != r)
	{
		num[t[a]]--;

		for (int i = 0; i < n; i++)
			if (num[i] == 0 && i != a)
				ans += solve(i);
	}

	cout << ans;

	return 0;
}

pichulia 6년 전 1

추측건데 r에다가 root 번호를 저장하고 싶으셨던거같네요. 근데 지금은 root보다 1 작은 값을 넣고있어요.

csh519 6년 전 0

아 네 맞아요 37번 라인에 r = i - 1; 이라고 코딩을 제가 바꿨었거든요.

처음에는 r = i; 라고 코딩했었는데.. 이게 제 작업환경에서 실행시켜보니 자꾸 i + 1 값이 들어가더라구요.

방금도 컴파일 하면서 확인했는데 if 문안에서는 분명히 i 값이 들어가는데 if 문을 빠져나오면서 부터 i+1 값이 들어가더라구요....

비주얼 스튜디오 15를 쓰는데.. 컴을 오래켜놔서 그런가 뭔가 메모리 오류 같은게 있는 것 같습니다.

r = i 로 바꿔서 제출하니 바로 맞았습니다 뜨네요.. 일단 전 재부팅하러.. ㅎㅎ 답변 감사합니다.

csh519 6년 전 0

아 찾았습니다...

VS 15 에서 전역변수로

int n, t[51], num[51], a, r, ans; 과 같이 선언하면 뭔가 메모리 할당에 문제가 있는 것 같습니다.

int n, a, ans, r, t[51], num[51]; 다음과 같이 바꿔주니 문제가 해결되네여... 허허

pichulia 6년 전 1

전 원인을 알거같습니다

num[a]++; 를 해주셨는데

a 값이 -1이 될 수 있습니다.

우연찮게 num 배열의 바로 앞에 r 변수에 대한 정보가 저장되있어서

num[-1]++ 하면서 r 값이 1 커진거 같네요.

csh519 6년 전 0

아.. 그게 문제였군요.

앞으로 배열 인덱스에 더 신경써서 해야겟네요! 감사합니다!

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

문제

문제

출처

ICPC

트리 문제 질문입니다.

csh519 6년 전 0

pichulia 6년 전 1

csh519 6년 전 0

pichulia 6년 전 1

csh519 6년 전 0

csh519 6년 전 0

pichulia 6년 전 1

csh519 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말