글 읽기 - 도와주세요.. 틀렸습니다

kengh2472 5년 전 0

in배열은 node를 입력받는 배열입니다. gr배열은 그래프를 표시한 배열로 0,1을 좌, 우로 표시하였습니다.

dfs함수를 통해 좌, 우를 탐색해 가며 답을 뽑아냅니다.

제가 문제를 잘못이해하고 있는건가요.. 도움 부탁드립니다.

#include<iostream>

using namespace std;

int N, in[10002], gr[1000002][2];

void dfs(int node) {
	//좌측
	if (gr[node][0] != 0)
		dfs(gr[node][0]);
	//우측
	if (gr[node][1] != 0)
		dfs(gr[node][1]);
	
	printf("%d\n", node);
}

int main(void) {
	int input, index = 1;
	//root에 도달했을 때 우측 subtree를 위해 초기화
	in[0] = 987654321;
	while (scanf("%d",&input) != EOF){
		//root 입력
		if (index == 1)
			in[index++] = input;
		//tree 만드는 부분
		else {
			//이전 입력보다 작다면 좌측 subtree
			if (in[index - 1] > input) {
				gr[in[index - 1]][0] = input;
			}
			//아니라면 우측 subtree
			else {
				int i;
				for (i = index - 1; i >= 0; i--) {
					if (in[i] > input) {
						gr[in[i + 1]][1] = input;
						break;
					}
				}

			}
			in[index++] = input;
		}
	}

	//dfs
	dfs(in[1]);

	return 0;
}

njw1204 5년 전 1

반례입니다.

1
2
3

kengh2472 5년 전 1

아.. 위에코드로 해버리면 2를 다시 3으로 덮어씌어 버리네요.

우측 subtree의 값을 넣을 때, 루트를 찾아가는 방식으로 바꾸어서 통과하긴 했지만 다른분들의 코드보고 다시 공부하겠습니다.

감사합니다.

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

문제

문제

출처

ICPC

도와주세요.. 틀렸습니다

kengh2472 5년 전 0

njw1204 5년 전 1

kengh2472 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말