[BOJ] 1068:트리

0. 문제

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

1068번: 트리

 

1. 문제분석

- 트리라는 자료구조의 특성을 잘 알고 있다면 어렵지 않게 풀 수 있는 문제로, 트리가 가지고 있는 특성을 통해 리프노드를 찾기 위해서는 dfs를 사용해 문제를 풀어야 함을 알 수 있다.

• 트리는 cycle이 존재하지 않는 그래프이다.
• 하나의 트리는 하나의 루트만 존재한다. 루트가 여러 개라면 그것은 트리가 여러 개인 forest.
• 트리는 방향성이 존재하는(부모-자식) 그래프다. 

- 리프 노드가 자식이 없는 노드라는 말은, 방향성 그래프인 트리에서 더이상 dfs를 진행할 수  없는 노드가 리프노드가 된다는 뜻이기도 하다.

2. 주의할 점

- 전체 트리에서 일부 트리를 제거하게 되었을 때 바뀌는 트리의 모양과 그 때에 새롭게 발생하는 리프노드에 대해서 생각해보아야 한다. 

- 트리의 특성에 대해서 다시 한번 생각하자. 트리는 단 하나의 루트 노드만 갖는다. 이런 특징을 간과하면 문제를 괜히 더 어렵게 풀 수 있다. 

 

3. 소스코드(Java)

// boj 1068 : 트리
// dfs, 트리

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

public class boj_1068 {
    private static final int MAX = 50 + 1;
    private static int n;
    private static int root;
    private static int toDelete;
    private static LinkedList<Integer>[] graph;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        graph = new LinkedList [n];

        for (int i = 0; i < n; ++i) graph[i] = new LinkedList<Integer>();
        st = new StringTokenizer(br.readLine());
        for (int child = 0; child < n; ++child) {
            int parent = stoi(st.nextToken());
            if (parent < 0) {
                root = child;
                continue;
            }
            graph[parent].add(child);
        }
        toDelete = stoi(br.readLine());

        System.out.print(dfs(root));
    }

    private static int dfs(int start) {
        if (start == toDelete) return 0;
        if (graph[start].isEmpty()) return 1;
        int ret = 0;
        for (int child : graph[start]) {
            if (graph[start].size() == 1 && child == toDelete) ret++;
            else ret += dfs(child);
        }
        return ret;
    }

    private static int stoi(String s) {return Integer.parseInt(s);}

}

4. 여담

- dfs로 풀다보니 visited를 사용하려고 부던히 애썼으나 결국 실패. visited 없는 dfs도 있는 것!

- 트리의 특성처럼 기본적인 data structure 지식에 대해 다시 한번 고민해 볼 필요가 있다.