[자바] 백준 1068 - 트리

문제 쉽게 생각했는데, 4번째 시도에서야 성공했다.

 

도저히 모르겠어서 결국 결정적인 아이디어는 아래 블로그에서 참고했다. 

슬프게도 거의 보고서 코드를 썼는데도 바로 정답이 안 나왔다.

 

soboruya.tistory.com/34

[백준 1068] 트리(JAVA)

첫 번째는 런타임 에러 났는데, 이진 트리라고 생각하고 풀어서 난거라 자세히 보지도 않았고

두 번째는 getResult() 메소드에서 아래처럼 자식노드의 개수가 0이 아닐 때 카운트하라고 잘못 짜서 났다

 private static int getResult() {
	int cnt=0;
	for(int i=0;i<N;i++) {
		if(tree[i][0]!=removed && tree[i][1]!=0) cnt++;
	}
		
	return cnt;
		
}

 

세 번째는 반례 다 입력해봐도 틀린 게 없어서 오래 고민했다. 

그러다가 데이터 입력받는 부분에서 오류가 있는 걸 발견했다.

-1이 들어온 경우(루트 노드인 경우)에도 tree[i][0]에 parent값을 받아주어야 제거대상이 0인 경우에 루트노드가 제거되지 않는데, 그 로직을 건너 뛰어 버렸으니 에러가 난 것. 

 for(int i=0;i<N;i++) {
	parent = Integer.parseInt(str[i]);
	if(parent==-1) continue;
			
	//현재 tree의 0번에 parent 값 넣고 
	tree[i][0] = parent;			
	//parent tree의 1번에 자식노드 개수 ++
	tree[parent][1]++;
 }

 

아래처럼 순서만 옮겨주었더니 바로 통과했다. 

 for(int i=0;i<N;i++) {
	parent = Integer.parseInt(str[i]);
	//현재 tree의 0번에 parent 값 넣고 
	tree[i][0] = parent;
	if(parent==-1) continue;
	
	//parent tree의 1번에 자식노드 개수 ++
	tree[parent][1]++;
 }

 

전체 코드

 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int[][] tree;
	static int N;
	static int removed = -99;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		tree = new int[N][2]; //0:부모노드 번호, 1:자식노드 개수
		
		String[] str = br.readLine().trim().split(" ");
		int parent;

		for(int i=0;i<N;i++) {
			parent = Integer.parseInt(str[i]);
			if(parent==-1) continue;
			
			//현재 tree의 0번에 parent 값 넣고 
			tree[i][0] = parent;			
			//parent tree의 1번에 자식노드 개수 ++
			tree[parent][1]++;
		}
		int remove = Integer.parseInt(br.readLine().trim());
		removeNode(remove);		
		int result = getResult();
		System.out.println(result);

	}

	private static int getResult() {
		int cnt=0;
		for(int i=0;i<N;i++) {
			if(tree[i][0]!=removed && tree[i][1]==0) cnt++;
		}
		
		return cnt;
		
	}

	private static void removeNode(int remove) {
		
		int parent = tree[remove][0];
		if(parent!=-1) tree[parent][1]--; //부모노드의 자식수 --
		
		tree[remove][0]= removed; //지워졌다고 표시
		
		if(tree[remove][1]!=0) { //자식노드가 존재한다면 
			for(int i=0;i<N;i++) {
				if(tree[i][0]==remove) {
					removeNode(i);
				}
			}			
		}
	}
}