백준 1068번 트리 :: 마이구미

이번 글은 백준 알고리즘 1068번 문제 "트리" 를 다뤄본다.

문제명 그대로 트리 문제이다.

백준 알고리즘 1068번 트리

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

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이 때, 1번을 제거한다고 하면, 다음과 같이 된다.

위 그림과 같이 1번을 제거한다면 리프노드는 2번 노드 하나밖에 남지 않는다.

만약 3번을 제거한다면 2번, 4번 노드가 남아 2개의 리프노드가 남게 된다.

그렇다면 0번이 제거된다면, 리프노드는 0개가 되는 것이다.

즉 제거되는 노드의 자식들을 함께 제거한다.

문제는 생각보다 간단하다.

결국 제거되는 노드와 연결되어있는 자식들을 제거하면 된다.

다른 사람들은 쉽게 배열만으로 풀었지만, 본인은 머리가 잘 안돌아갔다.

본인은 BFS로 문제를 해결했다.

먼저 입력으로 주어진 수를 어떻게 트리로 만드는 지 보자.

주어지는 입력은 각 노드의 번호에 따른 부모의 번호가 주어지고 있다.

-1 0 0 1 1이 주어졌을 경우 위와 같은 트리가 나온다.

3 0 0 -1 1 은 어떻게 트리가 나올까?

위와 같이 트리가 만들어진다는 것만 이해한다면 크게 어려울 게 없다.

트리는 부모 배열과, 인접 리스트를 통해 만들어보겠다.

부모 배열

for(int i=0;i<n;i++) {
    int v = sc.nextInt();

    parent[i] = v;
}

주어지는 입력을 통해 노드의 번호에 따른 부모를 저장한다.

인접리스트

int root = 0;
for(int i=0;i<n;i++) {
    int v = parent[i];

    if (v == -1) {
        root = i;
        continue;
    }

    a[v].add(i);
    a[i].add(v);

}

부모 배열을 활용하여 인접리스트를 만들었다.

root는 주어지는 입력에 따라 다르기 때문에 root의 위치를 따로 저장해둔다.

그리고는 이제 탐색을 활용하면 된다.

1. 탐색을 통해 제거할 노드의 번호와 자식들을 제거한다..

2. 루트부터 모든 노드를 탐색하여 리프노드를 조사한다.

위 2가지 처리만 해주면 된다.

결국 노드 제거를 위한 탐색 후 리프노드를 찾기 위한 탐색으로써, 2번의 탐색을 통해 문제를 해결할 수 있다.

while(!q.isEmpty()) {
    remove = q.poll();
    boolean flag = false;

    for(int v : a[remove]) {
        if (!c[v] && parent[remove] != v) {
            q.add(v);
            c[v] = true;
            flag = true;
        }

    }

    if (!flag) {
        cnt++;
    }

}

기본적인 BFS 탐색을 이용한다.

조건을 부모 번호가 저장되어있는 배열을 활용하여 자식이 부모를 탐색하는 일을 배제했다.

인접리스트를 통해 탐색이 이루어지지 않는 경우는 flag를 통해 리프노드라고 판단했다.

전체 소스는 Github URL을 통해 확인하길바란다.

본인은 입력하는 부분이 너무 헷갈려서 처음에 힘들었다.

주어지는 입력부분을 잘 이해하고 푼다면 어려움이 없을 것이다.

백준 알고리즘 1068번 트리 전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/1068.java