06.트리 (Tree)

06.트리 (Tree)

트리란?

Graph 의 특수한 형태
모두가 연결되어 있는 그래프
- 어떤 두 점을 골라도 간선을 타고 사이를 이동 가능
사이클이 존재하지 않음
정점의 개수 (V) = 간선의 개수 (E) + 1

트리 문제의 Keyword

즉 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려한다.
즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 모든 마을은 연결되어 있다.
문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)

트리를 저장하는 방법

트리는 대부분 인접 리스트로 저장
- 공간 복잡도 이슈 때문에

	인전 행렬	인접 리스트
A와 B를 잇는 간선 존재 여부 확인	O(1)	O(min(deg(A), deg(B)))
A와 연결된 모든 정점 확인	O(V)	O(deg(A))
공간 복잡도	\(O(𝑉^2)\)	O(E)

트리 문제의 핵심

정점(Vertex) 와 간선(Edge) 에 대한 정확한 정의
트리의 요소와 문제의 요구 사항 매치

백준 11725번 - 트리의 부모 찾기

시간, 공간 복잡도 계산하기
- Root 를 시작으로 하는 그래프 탐색 문제
  - 탐색 알고리즘 : BFS or DFS
    - 인접 리스트를 쓴다면 O(V+E)
    - DFS 가 매우 쉽게 구현할 수 있다.
구현

public class baekjoon11725 {

    static int N;
    static ArrayList<Integer>[] graph;
    static int[] parent;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        graph = new ArrayList[N + 1];
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[x].add(y);
            graph[y].add(x);
        }

        dfs11725(1, -1);


        for (int i = 2; i < parent.length; i++) {
            System.out.println(parent[i]);
        }


    }

    private static void dfs11725(int x, int par) {

        for (int y : graph[x]) {
            if (y == par) continue;
            parent[y] = x;
            dfs11725(y, x);
        }

    }

}

백준 4803번 - 트리

구현

public class baekjoon4803 {

    static ArrayList<Integer>[] graph;
    static int n, m, vertex_cnt, edge_cnt;
    static StringBuilder sb = new StringBuilder();

    static boolean[] visit;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testcase = 0;
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            if (n == 0 && m == 0) {
                break;
            }

            graph = new ArrayList[n + 1];
            visit = new boolean[n + 1];

            for (int i = 1; i <= n; i++) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                graph[x].add(y);
                graph[y].add(x);

            }

            int result = 0;
            for (int i = 1; i <= n; i++) {
                if (visit[i]) continue;
                vertex_cnt = 0;
                edge_cnt = 0;

                dfs4803(i);

                if (edge_cnt == (vertex_cnt - 1) * 2) result++;

            }


            sb.append("Case ").append(++testcase).append(": ");

            if (result == 0) {
                sb.append("No trees.\n");
            } else if (result == 1) {
                sb.append("There is one tree.\n");
            } else {
                sb.append("A forest of ").append(result).append(" trees.\n");
            }

        }
        System.out.println(sb);

    }

    private static void dfs4803(int x) {
        vertex_cnt++;
        edge_cnt += graph[x].size();
        visit[x] = true;
        for (int y : graph[x]) {
            if (visit[y]) continue;
            dfs4803(y);
        }

    }
    
}

백준 1991번 - 트리 순회

구현

public class baekjoon1991 {

    static int[][] graph;
    static int N;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        graph = new int[30][2];

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            char c = st.nextToken().charAt(0);
            int cur = (int) (c - 'A');
            for (int j = 0; j < 2; j++) {
                char ch = st.nextToken().charAt(0);
                if (ch != '.') graph[cur][j] = (int) (ch - 'A');
                else graph[cur][j] = -1;
            }
        }

        pre_order(0);
        sb.append("\n");
        in_order(0);
        sb.append("\n");
        post_order(0);

        System.out.println(sb);
    }

    static void in_order(int x) {
        if (x == -1) return;
        in_order(graph[x][0]);
        sb.append((char) (x + 'A'));
        in_order(graph[x][1]);
    }

    static void pre_order(int x) {
        if (x == -1) return;
        sb.append((char) (x + 'A'));
        pre_order(graph[x][0]);
        pre_order(graph[x][1]);

    }

    static void post_order(int x) {
        if (x == -1) return;
        post_order(graph[x][0]);
        post_order(graph[x][1]);
        sb.append((char) (x + 'A'));
    }


}

백준 15900번 - 나무 탈출

구현

public class baekjoon15900 {

    static int N, sum_leaf;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        graph = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[x].add(y);
            graph[y].add(x);

        }

        dfs15900(1, -1, 0);

        if (sum_leaf % 2 == 0) System.out.println("No");
        else System.out.println("Yes");
    }

    private static void dfs15900(int x, int prev, int depth) {
        if (x != 1 && graph[x].size() == 1) sum_leaf += depth;
        for (int y : graph[x]) {
            if (y == prev) continue;
            dfs15900(y, x, depth + 1);
        }

    }


}

백준 20364번 - 부동산 다툼

구현

public class baekjoon20364 {

    static boolean[] state;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        state = new boolean[N + 1];

        StringBuilder sb = new StringBuilder();

        while (Q-- > 0) {
            int x = Integer.parseInt(br.readLine());
            int y = x;
            int result = 0;

            while (x > 0) {
                if (state[x]) result = x;
                x >>= 1;
            }

            state[y] = true;

            sb.append(result).append("\n");

        }

        System.out.println(sb);
    }

}

백준 3584번 - 가장 가까운 공통 조상

구현

public class baekjoon3584 {


    static int N;
    static int[] per, check;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {

            N = Integer.parseInt(br.readLine());

            per = new int[N + 1];
            check = new int[N + 1];

            for (int i = 1; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                per[v] = u;
            }

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            while (x > 0) {
                check[x] = 1;
                x = per[x];
            }

            while (y > 0 && check[y] == 0) {
                y = per[y];
            }

            System.out.println(y);

        }

    }

}

백준 1240번 - 노드 사이의 거리

구현

public class baekjoon1240 {

    static ArrayList<int[]>[] tree;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        tree = new ArrayList[N + 1];

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

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            tree[x].add(new int[]{y, c});
            tree[y].add(new int[]{x, c});

        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            dfs1240(x, -1, y, 0);

        }


    }

    private static void dfs1240(int x, int prev, int goal, int dist) {
        if (x == goal) {
            System.out.println(dist);
            return;
        }

        for (int[] cur : tree[x]) {
            if (cur[0] == prev) continue;
            dfs1240(cur[0], x, goal, dist + cur[1]);
        }

    }

}

백준 9489번 - 사촌

구현

public class baekjoon9489 {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            if (N == 0 && K == 0) break;

            int[] tree = new int[N + 1], par = new int[N + 1];

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= N; i++) {
                tree[i] = Integer.parseInt(st.nextToken());
            }

            par[0] = -1;
            par[1] = 0;

            int last = 1;

            for (int i = 2; i <= N; i++, last++) {
                for (; i <= N; i++) {
                    par[i] = last;
                    if (i < N && tree[i] + 1 != tree[i + 1]) {
                        break;
                    }
                }
            }

            int findIdx = 0;
            for (int i = 1; i <= N; i++) {
                if (tree[i] == K) findIdx = i;
            }

            int result = 0;
            for (int i = 1; i <= N; i++) {
                if (par[par[i]] == par[par[findIdx]] && par[i] != par[findIdx]) {
                    result++;
                }
            }

            System.out.println(result);

        }

    }
}

백준 1068번 - 트리

정답의 최대치
- 단말의 노드 개수 ≤ 전체 정점의 개수 ≤ N Integer 범위 안에 들어온다
정점 제거 방법
- 그래프에서 정점이 사라진다?
- 정점과 이어진 간선들이 모두 사라진다
- 정점 x의 부모에서 x로 가는 간선을 삭제 or 무시 하자
트리의 단말 노드 개수를 세는 방법
- Root 에서 DFS를 한다면?
  - 어떤 노드 x에서 자식 노드 y에 대한 탐색을 끝내고 돌아오면 leaf[y] 값이 계산되어 왔을 테니, leaf[x] 에 leaf[y]를 누적해주면 된다.
시간, 공간 복잡고 계산하기
- Root 를 시작으로 하는 그래프 탐색 문제
  - 탐색 알고리즘 : DFS or DFS
    - 인접 리스트를 쓴다면 O(V+E)
    - DFS 가 매우 쉽게 구현 할 수 있다.
구현

public class baekjoon1068 {

    static int n, root, removal;
    static ArrayList<Integer>[] child;
    static int[] leaf;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        child = new ArrayList[n];
        leaf = new int[n];

        for (int i = 0; i < n; i++) child[i] = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            int par = Integer.parseInt(st.nextToken());
            if (par == -1) {
                root = i;
                continue;
            }
            child[par].add(i);
        }

        removal = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            if (child[i].contains(removal)) {
                child[i].remove(child[i].indexOf(removal));
            }
        }

        if (root != removal) dfs1068(root, -1);

        System.out.println(leaf[root]);

    }

    private static void dfs1068(int x, int prev) {
        if (child[x].isEmpty()) {
            leaf[x]++;
        }

        for (int y : child[x]) {
            if (y == prev) continue;
            dfs1068(y, x);
            leaf[x] += leaf[y];
        }

    }
}

백준 15681번 - 트리와 쿼리

구현

public class baekjoon15681 {

    static int N, R, Q;
    static ArrayList<Integer>[] tree;
    static int[] Dy;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());


        tree = new ArrayList[N + 1];
        Dy = new int[N + 1];

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

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            tree[x].add(y);
            tree[y].add(x);
        }

        dfs15681(R, -1);

        for (int i = 0; i < Q; i++) {
            int q = Integer.parseInt(br.readLine());

            System.out.println(Dy[q]);


        }

    }

    private static void dfs15681(int x, int prev) {
        Dy[x] = 1;
        for (int y : tree[x]) {
            if (y == prev) continue;
            dfs15681(y, x);
            Dy[x] += Dy[y];

        }

    }

}

백준 14267번 - 회사 문화1

구현

public class baekjoon14267 {

    static int N, M;

    static int[] Dy;

    static ArrayList<Integer>[] children;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        children = new ArrayList[N + 1];
        Dy = new int[N + 1];


        for (int i = 1; i <= N; i++) {
            children[i] = new ArrayList<>();
        }

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

        for (int i = 1; i <= N; i++) {
            int par = Integer.parseInt(st.nextToken());
            if (i == 1) continue;
            children[par].add(i);
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            Dy[x] += s;
        }

        dfs1427(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(Dy[i]).append(" ");
        }
        System.out.println(sb);

    }

    private static void dfs1427(int x) {

        for (int y : children[x]) {
            Dy[y] += Dy[x];
            dfs1427(y);
        }
    }


}

알고리즘 유형별 문제풀이

06.트리 (Tree)

06.트리 (Tree)

트리란?

트리 문제의 Keyword

트리를 저장하는 방법

트리 문제의 핵심

백준 11725번 - 트리의 부모 찾기

백준 4803번 - 트리

백준 1991번 - 트리 순회

백준 15900번 - 나무 탈출

백준 20364번 - 부동산 다툼

백준 3584번 - 가장 가까운 공통 조상

백준 1240번 - 노드 사이의 거리

백준 9489번 - 사촌

백준 1068번 - 트리

백준 15681번 - 트리와 쿼리

백준 14267번 - 회사 문화1

SIKSIK 의 개발 여행

Error

06.트리 (Tree)

트리란?

트리 문제의 Keyword

트리를 저장하는 방법

트리 문제의 핵심

Templates (for web app):

Error