[JAVA] BOJ(백준) - 트리 - 1068

문제내용

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

1068번: 트리

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

---

문제 접근 방법

입력값으로 트리가 주어지고 해당 트리에서 노드를 하나 삭제 했을때 삭제한 노드의 자식노드를 모두 지우고

트리에서 단말노드의 갯수를 구하는 문제이다.

 

나는 이 문제를 풀기위해 다음과 같은 방식으로 접근했다.

1. 입력값 이해하기
   먼저 입력값이 어떻게 이뤄졌는지 이해해야 한다.
   입력된 각각의 값은 몇번 노드와 연결돼있는지 알려준다. 다만 값이 -1일땐 루트노드를 의미한다.
   입력값이 1차원 배열로 이루어져 있다고 생각하면
   배열의 인덱스 = 노드번호
   배열의 요소값 = 몇번 노드에 연결됐는지 알려주는 값
   이라고 생각할 수 있다.
   
   
2. 간선 구하기
   코드상에서 트리를 구현하기 위해 어떤 노드들이 연결돼 있는가를 알아야 하고 이를위해 간선의 표시는 필수이다.
   따라서 간선을 표시해주는 작업이 우선이라 생각했다.
   간선을 표시하는 방법은 두가지다. 참고로 나는 이중리스트를 이용해서 간선을 표시했고
   이중리스트를 활용한 이유는 입력값이 정해진 길이가 아니고, 연결된 것만 표시할 수 있기때문에 배열보다
   메모리가 덜 든다.( 2차원 배열로 안해봤는데 메모리초과 날꺼같음 )
   1. 2차원 배열을 이용
      인덱스 = 노드번호
      요소값 = "1 과 -1" 로 표시해서 1일경우 간선존재, -1일경우 간선존재x
      로 표시한다.
   2. 이중리스트 이용
      리스트안에 리스트를 만들어서 큰리스트 에서 작은리스트로 연결돼있는지 여부를 나타낸다.
      연결이 돼있을땐 값을 큰리스트와 작은리스트에 각각 연결된 노드를 삽입해준다.
      이때는 배열과다르게 무조건 연결된것들만 표시할 수 있다.
3. 각 노드의 레벨 구하기
   각 노드의 레벨을 구하는 이유는 어떤 노드를 삭제 했을때 그 노드에 딸린 자식 노드를 모두 삭제하기 위해서이다.
   자식노드인지 아닌지를 알기위해선 간선만으로 알수 없고 해당 노드의 레벨을 통해 알아야 한다 생각해서 노드마다 레벨을 구해줬다. 이때 DFS를 활용해 레벨을 구해준다.
   각노드의 레벨은 해시맵에 노드번호=key, 노드레벨=value로 저장했다
4. target 노드 삭제 하기
   target노드와 연결된 자식 노드들을 삭제한다. 이때 노드를 삭제한다는 의미는 target 노드와 연결된 자식 노드들의 간선을 모두 제거한다는 의미와 같다.
   따라서 target노드를 기준으로 자식으로 연결된 노드들의 간선을 DFS를 이용해 이중리스트에서 값을 모두 제거해줬다. 그리고 제거하고 남은 간선에서 루트노드를 제외하면 이중리스트에서 값이 하나만 남은건 단말노드가 된다.
   
   다만 몇가지 간선을 제거할때 주의해야게 있다.
   
   1. target이 마지막 노드(단말 노드)일 경우
      이때는 DFS가 아니라 본인과 연결된 노드의 간선하나만 지우도록한다.
   2. target이 마지막 노드(단말 노드)이면서 전체노드가 2개인 경우
      한마디로 루트노드와 target노드만 존재하는 트리일 경우를 말한다.
      이때는 target노드와 연결된 노드의 간선을 모두지우면 리스트는 빈상태가 된다.
      따라서 target노드 본인꺼에서만 간선을 지우고 루트노드에서 간선은 남겨둬야한다.
   3. remove 메서드 사용할때 Integer 객체 활용하기
      리스트에서 remove 메서드는 두가지로 나뉜다.
      int를 인자로 주면 리스트내의 해당 인덱스를 찾아가 제거하고
      Integer는 객체이기 때문에 객체를 인자로 주면 리스트내에 해당 객체를 찾아가 제거한다.
      
      이걸 왜 주의해야 하냐면 내가짠 로직에선 노드번호를 기준으로 간선을 제거하는데 만약
      int로 remove를 해버리면 각 노드의 인덱스값이 바꼈을때 다음 노드를 제거할때 예외가 발생하기 때문이다.
      따라서 인덱스가 바뀌더라도 내가 원하는 노드를 지우기 위해선 객체를 넣어줘야한다.
5. 단말 노드 개수 찾기
   이때는 노드가 2개인것과 2개보다 많은것으로 나눠 찾는다.
   먼저 노드가 2개보다 많을때는 리스트를 돌면서 루트노드가 아닌 노드들 중에서 연결된 노드가 하나만 있는경우가 단말노드가 된다.
   
   그리고 노드가 2개보다 작거나 같을땐 단말노드는 루트노드 1개 밖에 안나온다.
   다만 target이 루트노드라면 당연히 트리가 사라지게 돼서 단말 노드는 0개가 나온다.

나는 1~5번과정을 차례대로 생각하며 풀었냈는데 설명이 어려워보인다.
코드를 보고 생각해보자..

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<ArrayList<Integer>> edge = new ArrayList<ArrayList<Integer>>();//인접리스트(간선표시)
	static HashMap<Integer, Integer> mapLevel = new HashMap<Integer, Integer>();//노드 레벨, key=인덱스(노드) , value=레벨
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];//인덱스 - 값 연결돼있음.
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(arr[i]==-1) mapLevel.put(i, 0);//부모노드 추가
		}
		
		int key = 0; //부모노드(인덱스,key)
		for(int k:mapLevel.keySet()) key = k;
		Integer target = Integer.parseInt(br.readLine());
		
		createEdge(arr);//1. 간선 만들기
		level(key);//2. 각 노드 레벨 표시
		deleteNode(target);//3. target과 연결된 노드의 간선 모두 제거
		System.out.println(findLeaf(arr));//4. 단말노드 개수 출력
		
		for(ArrayList<Integer> l:edge) {
			System.out.println(l);
		}
	}
	
	//1. 간선 만들기
	public static void createEdge(int[] arr) {
		for(int i=0; i<arr.length; i++) {//인접리스트 생성
			edge.add(new ArrayList<Integer>());
		}
		
		//간선 연결해주기
		for(int i=0; i<arr.length; i++) {
			if(arr[i]==-1) {continue;}//부모노드는 건너뜀
			int aNode = arr[i];
			int bNode = i;
			edge.get(aNode).add(bNode);
			edge.get(bNode).add(aNode);
		}
	}
	
	//2. 각 노드의 레벨 표시(DFS)
	public static void level(int v) {
		//간선 존재 여부로 노드 v에 연결된 노드를 모두 탐색하면서
		//탐색한 노드(i)가 아직 레벨 표시가 안돼있으면 표시해주기
		//이때 v는 부모 노드부터 시작하기 때문에
		//i의 value를 추가할땐 v노드의 value값+1로 해준다. 
		for(Integer i:edge.get(v)) {
			if(!mapLevel.containsKey(i)) {
				mapLevel.put(i, mapLevel.get(v)+1);
				level(i);
			}
		}
	}
	
	//3. target에 연결된 노드의 간선 모두 제거(DFS)
	public static void deleteNode(Integer target) {
		//간선을 가지고 target에 연결된 노드를 temp에 모두 추가.
		ArrayList<Integer> temp = new ArrayList<Integer>();
		for(Integer i:edge.get(target)) {
			temp.add(i);
		}
		
		//temp에 추가된 노드들을 전부 탐색하면서 간선에 연결된 노드 제거.
		for(int i=0; i<temp.size(); i++) {
			//target노드를 기준으로 자식노드들을 모두 없애준다.(자식 노드 있을때)
			if(mapLevel.get(temp.get(i))>mapLevel.get(target)) {
				edge.get(target).remove(temp.get(i));
				edge.get(temp.get(i)).remove(target);
				//자식노드를 기준으로 간선이 연결된 노드 계속 제거
				deleteNode(temp.get(i));
			}
			
			//edge.size()는 노드의 개수임. 
			//target노드에 연결된 간선이 1개면 마지막 노드라는 의미 (자식 노드 없을때)
			if(edge.size()>2 && edge.get(target).size()==1) {
				//target본인 노드를 지우고 간선에 의해 부모에 있는 target 노드를 지움.
				edge.get(target).remove(0);
				edge.get(temp.get(0)).remove(target);
			}else if(edge.size()<=2 && edge.get(target).size()==1) {
				//전체 노드가 2개이하 일땐 target본인 노드만을 지운다.
				//이유는 부모노드는 남겨놔야 하기때문에.
				edge.get(target).remove(0);
			}
		}
		
	}
	
	//4. 단말노드 개수 구하기
	public static int findLeaf(int[] arr) {
		int cnt = 0;
		
		//노드가 2개 보다 많을땐 모든 간선을 돌면서 부모노드를 제외하고
		//간선에 연결된 노드가 한개인 것들만 cnt++해줌( 그게 단말 노드임 )
		if(edge.size()>2) {
			for(int i=0; i<edge.size(); i++) {
				if(arr[i]!=-1 && edge.get(i).size()==1) cnt++;
			}
		}
		//그게 아닐땐
		//노드 사이즈가 한개인것만 cnt++해줌.
		//이때는 부모노드하나만 있어서 1로 나오거나,
		//부모노드를 target으로 했다면 0으로 나옴.
		else if(edge.size()<=2) {
			for(int i=0; i<edge.size(); i++) {
				if(edge.get(i).size()==1) cnt++;
			}
		}
		return cnt;
	}
}

---

마치며

이중리스트에 익숙하지 않다면 힘들수도 있는 문제라고 생각한다. 나도 그랬고..

이문제를 풀기전에 백준에서 "트리의 부모 찾기" 라는 문제를 먼저 풀어보는게 좋을것 같다.