[Baekjoon] 1068_트리

Gold V

문제(출처: https://www.acmicpc.net/problem/1068)

---

<트리>

문제 

 

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.

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

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

 

 

입력

 

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

 

출력 

 

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

 

 

문제 풀이

   - my solution (Python)

import sys

def delnode(graph, start):
    queue=[start]

    while queue:
        temp=queue.pop(0)
        for i in graph[temp]: # 지울 노드와 연결된 노드
            queue.append(i)

        del graph[temp]

if __name__ =='__main__':
    n=int(input()) # 노드의 개수

    graph={}
    for i in range(n):
        graph[i]=[]

    info=list(map(int, sys.stdin.readline().split())) # 각 노드의 부모

    for i in range(len(info)):
        if info[i]==-1: # 루트
            pass
        else:
            graph[info[i]].append(i)

    d=int(input()) # 지울 노드의 번호

    answer=0 # 리프 노드의 개수
    delnode(graph, d)

    for key,value in graph.items():
        if d in value: # 노드 지움
            graph[key].remove(d)
        if len(value)==0: # 리프 노드 개수
            answer+=1

    print(answer)

 

- my solution (JAVA)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int answer=0; //리프 노드의 개수
	
	static void delnode(HashMap graph, int d ) {
		List<Integer> queue=new ArrayList<>();
		queue.add(d);
		
		while(queue.size()!=0) { // queue가 빌 때까지
			int temp=queue.remove(0);
			List<Integer>a=(List<Integer>) graph.get(temp);
			if(a.size()>0) { // 지울 노드와 연결된 노드
				for(int i=0; i<a.size(); i++) {
					queue.add(a.get(i));
				}
			}
			graph.remove(temp);
			
		}
	}

	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		
		HashMap<Integer, List> graph=new HashMap<>();
		int n=input.nextInt(); // 노드의 개수
		
		for(int i=0; i<n; i++) { 
			List<Integer> a=new ArrayList<>();
			graph.put(i, a);
		}
		
		int info[]=new int[n];
		
		for(int i=0; i<n; i++) { // 각 노드의 부모
			info[i]=input.nextInt();
		}
		
		for(int i=0; i<info.length; i++) {
			if(info[i]==-1) { // 루트
				continue;
			}else {
				List<Integer>temp=graph.get(info[i]);
				temp.add(i);
				graph.put(info[i], temp);
			}
		}
		int d=input.nextInt(); // 지울 노드의 번호
		delnode(graph,d);
		
		graph.forEach((key, value) ->{
			if(value.contains(d)) { // 지울 노드의 번호가 포함되어있다면 삭제
				List<Integer> delkey=graph.get(key);
				delkey.remove(Integer.valueOf(d));
				graph.put(key, delkey);
			}
			if(value.size()==0) { // 리프 노드의 개수 추가
				answer+=1;
			}
		});
		System.out.println(answer);
	}
}

 

• delnode
  : 처음에 queue에 지울 노드의 번호를 담은 후 temp와 연결된 노드들을 queue에 담고 graph에서 temp를 키로 가진 것을 삭제
• Main
  :노드의 개수, 각 노드의 부모, 지울 노드의 번호 입력
  : answer = 리프 노드의 개수
  : graph = [key: 노드의 부모, value: 노드]
  : delnode 호출 (  graph, 지울 노드의 번호)
  : graph에는 지울 노드의 번호와 연결된 노드들을 지운 후의 상태로 존재. 지울 노드의 번호가 value에 존재하는지 확인 후 존재한다면 value에서 삭제. value의 길이가 0이라면 리프 노드이므로 answer +1

 

❓ 처음에 왜 틀렸는가?

지울 노드의 번호가 자식 노드에 있을때 자식 노드에서 삭제하는 것을 빼먹었기 때문이다. 맨 처음 작성한 코드는 지울 노드의 번호를 key값으로 가진 것을 삭제하며, 지울 노드의 번호와 연결된 노드들을 삭제하는 것이었다. 이 경우 지울 노드의 번호를 value로 가질 때 value에서 삭제하지 않아 답이 다르게 나왔던 것이었다.

 

---

생각🤔

 

오랜만에 JAVA로도 문제를 해결해봤다. 

먼저 Python으로 구현 후 JAVA로 구현하는 것임에도 오랜만이라 조금 오래 걸렸던 것 같다.

 

 

---