백준 - 트리(1068)

⭐ 문제링크

오늘은 트리 라는 문제를 가져왔다.

문제요약

트리를 구상하는데, 특정 node를 지웠을 때 leadNode는 몇 개인지 확인하는 문제이다.
여기서 지워진 node의 childNode들까지 모두 지워지는 것으로 간주한다.

문제접근

dfs로 하면 금방 풀 수 있지 않을까? 싶었다.

내 로직은 다음과 같다.

1. N개의 트리만큼의 List 배열을 생성한다.
2. 해당 배열에 각 노드의 자식들을 넣어준다.
3. 지워질 노드와 지워질 노드에 해당하는 자식들에 -1 이란 값을 넣는다.
4. 최종적으로 각 인덱스에 해당하는 배열의 size가 0인 것만 찾는다.

예를 들어

5
-1 0 0 1 1
2

라는 입력값이 있다는 가정 하에, 해당 트리는 아래와 같이 생겼다.

그리고 각 노드의 자식들을 표시해줄 List 배열은 다음과 같을 것이다.

[ NodeIdx : children ]
0 : 1, 2
1 : 3, 4
2 :
3 :
4 :

여기서 입력값으로 들어온 지워질 Node는 2이다.

그렇다면 List 배열을 아래와 같이 변화한다.

[ NodeIdx : children ]
0 : 1, 2
1 : 3, 4
2 : -1
3 :
4 :

최종적으로 for문을 돌며 각 List 배열 속 원소의 개수가 0인 것만 찾는다면, 문제가 원하는 leafNode의 개수를 찾을 수 있을 것이라 생각했다.

---

그러나!!

문제점이 하나 있다.

바로 "편향트리"인 경우이다.

만약 해당 트리가 주어진다고 가정한 후, Node 3이 지워진다고 가정해보자.

내 로직대로라면 최종적인 List 배열은 다음과 같을 것이다.

[ NodeIdx : children ]
0 : 1
1 : 2
2 : -1

여기서 문제점이 발생한다. 난 Node를 배열에서 직접 지우는 것이 아닌, -1 이란 값을 더 넣어 구분하려 했다. 그렇다보니 자식이 하나인데 해당 자식이 삭제 노드의 대상인 경우에 그 부모 노드 역시 leaf Node가 되어야 하는데 인식을 못하게 되는 것이다.

그래서 최종적으로는 모든 List 배열이 완성되고 난 후, if 문을 2가지 추가하여 정답을 도출해낼 수 있었다.

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static List<Integer> [] tree;
    public static void main(String[] args) throws IOException {

        int remove = init();
        dfs(remove);

        int answer = 0;
        for(int i=0; i<N; i++){
            if(tree[i].size()==0) { //list 배열의 원소개수 0 == 자식 노드 없다.
                answer++; 
            } //자식 노드가 1개 있지만, 삭제 대상이었다면
            if(tree[i].size()==1&&tree[i].get(0)==remove) answer++;
        }

        System.out.println(answer);
    }

    static void dfs(int idx) {
        tree[idx].add(-1); //본인에 -1 처리

        for(int i=0; i<tree[idx].size(); i++){
            int child = tree[idx].get(i);
            if(child==-1) break;
            dfs(child); //자식에 -1 처리
        }

    }

    static int init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        tree = new List[N];

        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            tree[i] = new LinkedList<>();
        }

        for(int i=0; i<N; i++) {
            int idx = Integer.parseInt(st.nextToken());
            if(idx==-1) continue;
            tree[idx].add(i);
        }

        return Integer.parseInt(br.readLine());

    }
}

---

그러나 해당 문제는 "트리"에 대한 문제였다. 그래서 트리를 구현해보고 해당 문제를 풀고 싶어서, 코드를 다시 작성해보기 시작했다.