[java]백준 1068번: 트리(트리, DFS)

트리
노드와 에지로 연결된 그래프의 특수한 형태

 

트리의 특징
- 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재
- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가지고 있음
- 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따름

 

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
서브 트리	전체 트리에 속한 작은 트리

 

---

https://www.acmicpc.net/problem/1068

1068번: 트리

 

정답 코드 2개

 

정답 코드 1

 

import java.util.*;

public class j1068 {
	static boolean[] noLeaf;
	static ArrayList<Integer>[] childs;
	static int[] myParents;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		noLeaf = new boolean[N];
		myParents = new int[N];
		childs = new ArrayList[N]; // 부모노드들의 자식노드
		for (int i = 0; i < N; i++) { // 초기화
			childs[i] = new ArrayList<>();
		}
		for (int i = 0; i < N; i++) { // 자식노드 넣어주기
			int parent = sc.nextInt();
			myParents[i] = parent;
			if (parent != -1) {
				noLeaf[parent] = true;
				childs[parent].add(i);
			}
		}

		DFS(sc.nextInt());
		int leafCount = 0;
		for (int i = 0; i < N; i++) {
			if (noLeaf[i] == false) {
				System.out.println("난 리프" + i);
				leafCount++;
			}
		}

		System.out.println(leafCount);

	}

	private static void DFS(int node) {

		// 자식노드들 삭제해주기
		for (int child : childs[node]) {
			DFS(child);
		}

		// 부모노드가 리프노드가 되는지 확인
		int parent = myParents[node];
		if (parent != -1) {
			// 자식노드가 하나를 삭제하면 리프노드이므
			if (childs[parent].size() == 1) {
				noLeaf[parent] = false;
			}
		}
		
		//자식노드 다 돌고서 삭제(자식노드가 하나일 때 리프노드라고 해줄까봐)
		noLeaf[node] = true;

	}

}

 

풀이

DFS로 트리 해결

1. 삭제 노드의 자식 노드들을 돌면서 noLeaf [노드]=true라고 해주며 리프 노드가 아님을 확인
2. 삭제 노드가 삭제되었을 때 부모 노드가 리프 노드 인지도 확인

 

책에서 정답 코드

import java.util.*;

public class j1068_2 {
	static ArrayList<Integer>[] tree;
	static boolean[] visited;
	static int answer =0;
	static int deleteNode=0;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		tree=new ArrayList[N];
		visited=new boolean[N];
		int root=0;
		for(int i=0;i<N;i++) {
			tree[i]=new ArrayList<>();
		}

		for(int i=0;i<N;i++) {
			int parent=sc.nextInt();
			if(parent !=-1) { //부모가 루트노드가 아닐 때
				tree[i].add(parent);
				tree[parent].add(i);
			}else {//루트노드
				root=i;
			}
		}
		
		deleteNode=sc.nextInt();
		
		if(deleteNode==root)// 삭제할 노드가 루트노드이면 트리가 전부 삭제되므로 리프노드 0
			System.out.println(0);
		else {
			DFS(root);
			System.out.println(answer);
		}
	}
	
	static void DFS(int node) {
		visited[node]=true;
		int cNode=0;
		for(int n:tree[node]) {
			if(visited[n]==false && n!=deleteNode) {// 삭제 노드일 때는 확인하지 않는다
				cNode++; // 자식노드가 있음을 확인
				DFS(n);
			}
		}
		if(cNode==0) { //자식노드가 없을 때 리프 노드로 간주하고 정답값 증가
			answer++;
		}
	}
}

 

풀이

DFS로 트리 해결

1. DFS로 삭제노드는 읽지 않으며 leaf노드를 확인