[백준 1068번] 트리 - java

문제 설명

1. 몇개의 노드가 주어질지 입력

2. 순서대로 노드가 주어진다.

3. 어떤 노드를 지울지 알려준다.

4. 그 노드랑 이 노드의 모든 자식노드를 지원 후 남은 자식노드 갯수 구하기

풀이 과정

1. 처음에는 그냥 어떤 노드의 자식들을 모두 보관하게 하고 그 노드를 기준으로 자식을 확인해가면서 삭제해줬다.

2. 그리고 ans는 처음에 모든 자식없는 노드들을 확인해서 만들어줬다.

3. 리프노드 도달시 하나씩 뺴줘서 처리했다.

4. 이랬더니 중간에 틀렸는데, 이유를 생각해보니 어떤 노드의 부모가 그 노드만을 자식으로 가진다면 문제가 될 것 같았다.

(O-O-O 이렇게 돼있으면 안됨)

5. 여러 방법이 있었겠지만... 나는 그냥 그 노드의 부모를 갖는 Map을 하나 더 만들어서 부모 찾고 자식이 하나뿐이면 더해주는 식으로 해결했다. <- 깔끔한 방법이 아니라 그냥 앳지케이스 핸들링

코드

import java.util.*;

public class Main
{
    private static Map<Integer, List<Integer>> parentMap = new HashMap<>();
    private static Map<Integer, Integer> findParent = new HashMap<>();
    private static int ans = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int count = Integer.parseInt(sc.nextLine());
        for (int i=0; i<count; i++) {
            int parent = sc.nextInt();
            findParent.put(i, parent);  // 지금 들어가는 노드의 부모를 찾는다.
            if(parent == -1) continue;
            List<Integer> children = parentMap.getOrDefault(parent, new ArrayList<Integer>()); // 어떤 노드의 자식들을 보관한다.
            children.add(i);
            parentMap.put(parent, children); // key: 부모, value: 자식
        }

        int remove = sc.nextInt();

        for(int i=0; i<count; i++) {
            if(!parentMap.containsKey(i)) ans++; // 자식이 없는 노드는 리프노드이다.
        }

        // 검색할 때에 이 부모가 하나의 자식밖에 없다면 이게 지워지면 그 부모가 리프노드가 된다.
        if(parentMap.getOrDefault(findParent.get(remove), new ArrayList<Integer>()).size() == 1) ans++;
        if(remove >=0 && remove < count) DFS(remove);

        System.out.println(ans);
    }

    // 삭제 대상 확인 DFS
    private static void DFS(int parent) {
        // 지금 이게 자식이 없는 노드이면 리프노드이므로 삭제처리
        if (!parentMap.containsKey(parent)) {
            ans--;
            return;
        }

        // 부모노드라면 자식들을 제거
        List<Integer> children = parentMap.get(parent);
        for(int child : children) DFS(child);
    }
}