글 읽기 - 혹시 문제 내용을 잘못 이해 한 건지... 조언 부탁드립니다

zinccccc 6년 전 0

코드는 다음과 같은 아이디어로 구현했습니다.

1. 입력받은 내용으로 이진 트리 구성

2. 각 노드를 조건에 맞게 R, G, B로 칠해보며, 마지막 노드가 칠해졌을 경우 주어진 K로 나누어 떨어지는지 확인.

3. 퇴각 검색하며 모든 노드 확인

테스트 케이스에 대해서는 답이 제대로 나오지만, 제출 시 런타임 에러가 발생합니다.

고민하다가 문제를 다시 읽어봤는데 주어진 테스트 케이스 입력값은 이진트리로 구성 가능하게 되어있지만,

입력 조건에는 그런 내용이 없더라구요ㅠㅠ...

테스트 케이스가 이진 트리가 아닌 3개 이상의 자식을 갖는 트리이거나 그래프일 수 있다고 가정하고 풀어야 하나요?

아니면 단순히 제 코드상의 문제인건지...

고수 분들의 조언 부탁드립니다ㅠㅠ

#include <cstdio>
#define RED		0
#define GREEN	1
#define BLUE	2
#define NONE	3
 
typedef struct TreeNode{
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;
	int colour;
	int val[3]; // RED, GREEN, BLUE
}TreeNode;
 
TreeNode trees[1001];
int val[1001][3]; // val[n][k] : the value of n'th socket (k could be one of the colours R, G, or B)
int V, Q, K, res;
 
/*
	Colour current node
	col : colour(one of RED, GREEN, BLUE, or NONE)
	cur : pointer of current node
	sum : sum of value before current node
	cnt : number of checked node
*/
void paint(int col, TreeNode* cur, int sum, int cnt)
{
	if( NULL != cur->parent )
	{
		if(cur->parent->colour == col && col == GREEN)
		{
			return;
		}
		if(cur->parent->colour == BLUE && col != GREEN) 
		{
			return;
		}
		if(cur->parent->colour != GREEN && col == BLUE)
		{
			return;
		}
	}
	sum+=cur->val[col];
	cur->colour = col;
	cnt++;

	if(cnt == V)
	{
		// coloured every socket
		if(0==sum%K)
		{
			res++;
			res%=Q;
		}
		cur->colour = NONE;
		return;
	}

	// traverse left child node
	if(NULL != cur->left)
	{
		// backtracking
		paint(RED, cur->left, sum, cnt);
		paint(GREEN, cur->left, sum, cnt);
		paint(BLUE, cur->left, sum, cnt);
	}
	else
	{
		while(1)
		{
			if(NULL != cur->right && NONE == cur->right->colour)
			{
				break;
			}
			cur = cur->parent;
		}
		// backtracking
		paint(RED, cur->right, sum, cnt);
		paint(GREEN, cur->right, sum, cnt);
		paint(BLUE, cur->right, sum, cnt);	
	}
	if(NULL != cur->right)
	{
		cur->right->colour = NONE;	
	}
	return;
}
 
int main() {
 
	scanf("%d %d %d", &V, &Q, &K);
 
	// initialise tree
	for(int i = 1; i < V; i++)
	{
		int first, second;
 
		scanf("%d %d", &first, &second);
 
		if(NULL == trees[first].left)
		{
			trees[first].left = trees+second;
		}
		else if(NULL == trees[first].right)
		{
			trees[first].right = trees+second;
		}
		trees[second].parent = trees+first;
		// else error
	}
	// initialise values of the each socket
	for(int i = 1; i <= V; i++)
	{
		scanf("%d %d %d", trees[i].val, trees[i].val+1, trees[i].val+2);
		trees[i].colour = NONE;
	}
 
	paint(RED, trees+1, 0, 0);
	paint(GREEN, trees+1, 0, 0);
	paint(BLUE, trees+1, 0, 0);
 
	printf("%d", res);
 
	return 0;
}

tae 6년 전 0

말씀하신 대로 문제에 이진 트리라는 언급은 없기 때문에 이진 트리를 가정하시면 안 될 것 같습니다. 예시 입력은 우연히 이진트리인 것 같아요. ㅠㅠ

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

문제

문제

출처

ICPC

혹시 문제 내용을 잘못 이해 한 건지... 조언 부탁드립니다

zinccccc 6년 전 0

tae 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말