[그래프] 백준 1068번 트리 - JAVA

 

DFS 문제 연습을 하려고 했는데 너무 어려워서

결국 그래프 연결로 풀고만 트리...ㅎ

 

이제 그래프 문제는 준마스터인 것인가?..

 

 

---

1. 출처

---

 

1068번: 트리

맞은 줄 알았는데, 78%에서 장렬히 틀렸던 순간...

끝까지 방심하지 말자 ^^

 

 

---

2. 설계

---

 

1) 트리를 구성하자

tree를 배열로 만들고, 한 배열에 ArrayList 자식들이 딸리게 만든다.

static List<Node>[] tree;

//트리 구성
int start = 0;
for(int i=0;i<N;i++) {
	int parent = sc.nextInt();
	if(parent==-1) start = i;//가장 최상단 노드임
	else tree[parent].add(new Node(i));
}

부모가 -1인 경우는 자기 자신이 최상단 노드이자 최고 부모라는 뜻이므로 start로 저장해준다.

이 가장 최상단 노드는 시작값으로 큐에 넣어줄 예정이다.

 

위 tree의 형태는 예제가 다음과 같을 때,

5
-1 0 0 1 1
2

다음과 같이 구성된다.

 

부모 [0] : 자식1, 자식2

부모 [1] : 자식3, 자식4

부모 [2] : 자식 없음

 

 

2) 큐를 활용하자

static Queue<Node> q;

//첫 시작 노드 큐에 넣어주기
q.add(new Node(start));

큐를 어떻게 활용할 것이냐면, 첫 시작 노드를 넣고, 시작하여 첫 시작 노드에 인접한 노드들을 큐에 모두 넣어줄 것이다.

이 때 인접 노드로 삭제한 노드가 튀어나오면 큐에 넣어주지 않기 때문에 그 자식들도 나올 일이 없게 만드는 것이다.

 

[잘못된 설계]

public static void leafNode() {
		while(!q.isEmpty()) {
			Node cur = q.poll();
			if(tree[cur.num].size()==0) countLeaf++; //여기서 끝 노드를 추가해주는것
            
			int count=0;
			for(int i=0;i<tree[cur.num].size();i++) {
				Node next = tree[cur.num].get(i);
				if(next.num==remove) continue;
				count++;
				q.add(new Node(next.num));
			}
		}
	}

근데 이 로직에서 중요한 건 리프 노드 수를 세어주는 조건과 타이밍이다.

처음에는 연결된 자식 노드가 없을 경우 if(tree[cur.num].size()==0) 일 때만 추가해줬는데, 다음 반례를 보니 내 실수를 깨달았다. 내가 왜 78%에서 틀렸습니다가 떴는지 바로 이해했다.

 

2
-1 0
1
ans: 1

 

1번 노드를 지웠음에도 내가 초기에 짠 코드에 의하면 0과 연결된 1번 노드가 지워지지 않고 그대로 있으니 리프노드로 인식하지도 않을 뿐더러 for문에서도 continue만 띄워줄 뿐이여서 내 코드의 답은 0이 나왔던 것이다...  

 

 

public static void leafNode() {
		while(!q.isEmpty()) {
			Node cur = q.poll();
            
			int count=0;
			for(int i=0;i<tree[cur.num].size();i++) {
				Node next = tree[cur.num].get(i);
				if(next.num==remove) continue;
				count++;
				q.add(new Node(next.num));
			}
			
			//현재 노드에서 자식 노드들이 하나도 안지워졌거나 count ==0
			//아예 자식이 없었다면 끝노드로 생각하고 추가
			if(count==0 || tree[cur.num].size()==0) countLeaf++;
		}
	}

때문에 실질적으로 count 변수를 이용해서 현재 노드에서 자식의 수가 추가 되었는지 확인해주고, 현재 노드에서 자식 노드들이 하나도 안지워졌다면 리프노드로 판단한다고 하였다.

 

또는 아예 for문에 안들어가고, 자식 노드가 없었을 경우에도 리프노드로 판단해주었다.

 

근데 이제보니 size가 애초에 0이면 for문에 안들어가니 어차피 count=0이여서 tree[cur.num].size()==0 조건을 빼도 된다.

 

 

그래도 해답이 풀리지 않는다면 아래 사이트에서 반례들을 모두 돌려보며 자신의 코드의 헛점을 파악할 것을 추천한다.

https://www.acmicpc.net/board/view/112681

글 읽기 - 반례모음

 

 

---

3. 전체 코드

---

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static List<Node>[] tree;
	static Queue<Node> q;
	static int remove, countLeaf;
	
	static class Node{
		int num;

		public Node(int num) {
			super();
			this.num = num;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();//트리의 노드 개수
		
		//초기화
		q = new LinkedList<>();
		tree = new ArrayList[N];
		for(int i=0;i<N;i++) {
			tree[i] = new ArrayList<>();
		}
		
		
		//트리 구성
		int start = 0;
		for(int i=0;i<N;i++) {
			int parent = sc.nextInt();
			if(parent==-1) start = i;//가장 최상단 노드임
			else tree[parent].add(new Node(i));
		}
		
		//첫 시작 노드 큐에 넣어주기
		q.add(new Node(start));
		
		//지울 노드 받기
		remove = sc.nextInt();
		
		//만약 start를 지우면 바로 0개 끝
		if(start==remove)countLeaf=0;
		else {
			leafNode();
		}
		
		System.out.println(countLeaf);
		
	}
	
	public static void leafNode() {
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			int count=0;
			for(int i=0;i<tree[cur.num].size();i++) {
				Node next = tree[cur.num].get(i);
				if(next.num==remove) continue;
				count++;
				q.add(new Node(next.num));
			}
			
			//현재 노드에서 자식 노드들이 하나도 안지워졌거나 count ==0
			//아예 자식이 없었다면 끝노드로 생각하고 추가
			if(count==0 || tree[cur.num].size()==0) countLeaf++;
		}
	}
}

 

---

오늘은 내 생일...

그래도 알고리즘 문제를 게을리 할 수 없지...

행복한 미래를 위하여 화이탱!!!