[JAVA] 백준 트리 뿌수기1

 

 

다익스트라에 이어 트리를 뿌숴보겠다.

bfs, dfs, dp 등을 익혔지만 가장 기초인 트리는 아직 정복하지 못했다는 걸 알았다.

이번에는 트리를 정복해보겠다.

 

 

트리(tree)란?

• 계층적 자료를 표현하는데 사용되는 자료구조
• 구성요소
  • 루트노드
  • 단말노드
  • 비단말노드
  • 간선
  • 차수 = 자식개수
  • 레벨 = 루트부터 1 시작
  • 트리높이 = 최대레벨
  • forest = 트리들 집합
• 종류
  • 포화 이진트리 = 각 레벨에 노드가 꽉 차있음
  • 완전이진트리 = 왼쪽부터 오른쪽으로 노드가 차있는 트리

 

 

 

트리순회

• 전위순회: 중 왼 오
• 중위순회: 왼 중 오
• 후위순회: 왼 오 중

 

 

 

최소신장트리(MST, Minimum Spanning Tree)

• 최소 연결 부분그래프
• 모든 정점을 연결시키고, 사이클을 포함해서는 안됨
• 가중치의 합이 최소/ n-1개의 간선만을 활용/ 사이클이 포함되면 안됨
• 풀이법
  • 크루스칼 MST알고리즘
  • Prim MST 알고리즘 

 

 

 

바로 활용

사실 트리는 글쓴이가 대학교에서 배운 내용이다. 이미 아는 내용이니 개념을 깊게 정리하기보단 바로 풀어보고 개념을 정리해보겠다!

 

 

 

 

9372 상근이의 여행 - 실버4

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

9372번: 상근이의 여행

• 사실 몰라서 구글링했다
• 최소신장트리에 대해 조금의 지식이 있는지 확인하는 문제
• 모든 정점을 연결하는 최소 간선의 수를 구하면 된다

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int tc =0; tc<tcCnt; tc++) {
            StringTokenizer st=  new StringTokenizer(br.readLine());
            int countryCnt = Integer.parseInt(st.nextToken());
            int flightCnt = Integer.parseInt(st.nextToken());

            for (int i =0; i<flightCnt; i++) {
                br.readLine();
            }

            sb.append((countryCnt-1) + "\n");
        }

        System.out.print(sb);
    }
}

• 노드수-1 이 정답

 

 

 

11725 트리의 부모 찾기 - 실버2

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

11725번: 트리의 부모 찾기

• 일단 다 연결하고 bfs느낌으로 부모를 저장하고 그대로 출력했다
• 트리인척 하는 bfs, dfs 문제!

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int nodeCnt = Integer.parseInt(br.readLine());

        ArrayList<Integer>[] arr = new ArrayList[nodeCnt];

        for (int i = 0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<nodeCnt-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            arr[a].add(b);
            arr[b].add(a);
        }

        boolean[] visited = new boolean[nodeCnt];
        int[] parent = new int[nodeCnt];

        Queue<Integer> queue = new PriorityQueue<>();
        queue.add(0);
        visited[0] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            for (int child: arr[curr]) {
                if (!visited[child]) {
                    visited[child] = true;
                    parent[child] = curr;
                    queue.add(child);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i =1; i<parent.length; i++) {
            sb.append(parent[i] + 1);
            sb.append("\n");
        }

        System.out.print(sb);
    }
}

• 연결리스트로 받음
• 1부터 queue에 넣고 visited를 체크하면서 자식을 탐색, 자식은 자신의 부모를 parent배열에 저장함
• parent를 순회하며 출력

 

구글링해보니 다른 사람들도 비슷하게 풀었다

 

 

 

 

 

1991 트리순회 - 실버1

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

1991번: 트리 순회

• 그냥 순회결과 출력하는 문제다
• 재귀호출만 잘해주면 될 것 같다

 

내 풀이

class Node {
    char name;
    Node left;
    Node right;

    public Node(char name, Node left, Node right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }
}

public class Main {
    static Map<Character, Character[]> map;
    static Node root;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        map = new HashMap<>();

        for (int i =0; i<nodeCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char root = st.nextToken().charAt(0);
            Character left = st.nextToken().charAt(0);
            Character right = st.nextToken().charAt(0);
            if (left == '.') {
                left = null;
            }

            if (right == '.') {
                right = null;
            }

            map.put(root, new Character[]{left, right});
        }

        root = findNode('A');

        preOrder(root);
        System.out.println();
        centerOrder(root);
        System.out.println();
        reverseOrder(root);
        System.out.println();
    }

    private static void reverseOrder(Node node) {
        if (node == null)
            return;

        reverseOrder(node.left);
        reverseOrder(node.right);
        System.out.print(node.name);
    }

    private static void centerOrder(Node node) {
        if (node == null)
            return;

        centerOrder(node.left);
        System.out.print(node.name);
        centerOrder(node.right);
    }

    private static void preOrder(Node node) {
        if (node == null)
            return;

        System.out.print(node.name);
        preOrder(node.left);
        preOrder(node.right);
    }

    private static Node findNode(Character name) {
        if (name == null) {
            return null;
        }

        Character[] arr = map.get(name);
        return new Node(name, findNode(arr[0]), findNode(arr[1]));
    }
}

• 전위순회 등등은 재귀호출로 쉽게 구현할 수 있었지만 트리만드는 게 조금 까다로웠다(익숙하지 않아서 그런듯)
• 노드마다 순서가 다르게 들어올 수 있었기 때문에 노드 각각의 이름에 맞는 map을 구현해줬다
• 그리고 루트노드를 만들면서 좌우 노드를 찾아 연결시켰다

 

 

다른사람의 풀이도 찾아봤다. 크게 2가지로 나뉘는듯

1. 입력을 받으면서 바로 트리를 연결하는 방법
   • 순서가 바뀌는 경우를 고려하지 않은 것 같다
   • https://velog.io/@gandi0330/Java-%EB%B0%B1%EC%A4%80-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-1991%EB%B2%88
2. N+1 길이의 배열을 생성하여 -'A'를 해준 뒤 각 인덱스를 Node저장소로 사용
   • A부터 Z까지로 확정이 되어있으니 각 인덱스를 고유저장소로 사용해도 상관이 없을 것 같다
   • 입력을 받으면서 바로 저장할 수 있을듯
   • 내가 사용한 해시랑 비슷한 느낌이다
   • 대부분의 사람들이 이와 같은 풀이로 풀었다. 이게 정석풀이인가? 강의나 책이 있는 게 아닌가 의심됨
   • https://hoehen-flug.tistory.com/48

 

 

 

 

9934 완전 이진 트리 - 실버1

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

9934번: 완전 이진 트리

• 전위순회 결과가 출력되었을 때 다시 트리를 원복시키면 된다
• 좌하부터 dfs로 찾으려고 했는데, 그것보단 그냥 전위순회 하면서 그때그때 채우는 게 좋아보여 그렇게 구현했다

 

public class Main {
    static int[] arr;
    static int k;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int count = (int)Math.pow(2, k) - 1;

        arr = new int[count+1];

        preOrder(1);

        int start = 1;
        int cnt = 1;
        for (int c =1; c<=k; c++) {
            for (int j=start; j<start+cnt; j++) {
                System.out.print(arr[j]+ " ");
            }
            System.out.println();
            start += cnt;
            cnt *= 2;
        }
    }

    private static void preOrder(int start) {
        if (start >= arr.length) {
            return;
        }

        preOrder(start * 2);

        if (arr[start] == 0) {
            arr[start] = Integer.parseInt(st.nextToken());
        }

        preOrder(start * 2+1);
    }
}

• 그냥 전위순회 그대로 하면 된다
• 그때그때 채워넣으면 됨

 

 

다른풀이도 찾아봤다

1. 재귀를 활용, 트리높이당 배열생성, 층마다 해당하는 노드 번호를 추가
   • 상상도 못한 기발한 풀이다! 한 번 코드를 직접보면 재밌을 것 같다
   • https://lotuslee.tistory.com/100
   • 현재 노드 번호와 높이를 넣어주면서 배열의 위치를 계산한다.
   • 배열의 위치를 이진탐색하듯이 찾고, 해당 높이의 배열에 노드를 삽입한다.
2.  이 분들도 depth를 계산하며 노드를 삽입하였다
   • https://kdw999.tistory.com/m/165
   • https://loosie.tistory.com/469
   • https://tussle.tistory.com/887
   • https://rovictory.tistory.com/121

 

나는 모두 나처럼 풀었을 줄 알았는데 바이블 풀이가 있었다... 다 똑같은 방법으로 푼 게 신기하다

 

 

 

 

14675 단절점과 단절선 - 실버1

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

14675번: 단절점과 단절선

• 일단 입력으로 주어지는 트리부터 만들고
• 단절점 질의에서는 해당 노드의 자식이 있는 경우 단절점이다
• 단절선 질의는 현재 입력값이 트리로 확정이기 때문에 무조건 yes를 출력해야한다. 

 

public class Main {
    static ArrayList<Integer>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<nodeCnt-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a =Integer.parseInt(st.nextToken())-1;
            int b =Integer.parseInt(st.nextToken())-1;
            arr[a].add(b);
            arr[b].add(a);
        }

        int questionCnt = Integer.parseInt(br.readLine());
        for (int i =0; i<questionCnt; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int idx = Integer.parseInt(st.nextToken())-1;

            if (t == 1) {
                if (arr[idx].size() >= 2) {
                    System.out.println("yes");
                } else {
                    System.out.println("no");
                }
            } else {
                System.out.println("yes");
            }
        }
    }
}

• 트리를 구성하진 않았다
• 해당 정점에 연결된 정점이 2개이상 있으면 단절점이고, 1개만 있으면 리프노드로 단절점이 아니다
• 단절선은 트리이기 때문에 간선이면 무조건 단절선이다. 

 

 

 

 

15900 나무 탈출 - 실버1

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

15900번: 나무 탈출

• (인섭이가 제일 나쁜듯)
• 모든 리프노드에서 루트까지의 거리의 합을 구한다
• 짝수면 못이기고 홀수면 이김

 

public class Main {
    static ArrayList<Integer>[] arr;
    static boolean[] visit;
    static long diff = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());
        StringTokenizer st;
        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }
        visit = new boolean[nodeCnt];

        for (int i=0; i<nodeCnt-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;

            arr[a].add(b);
            arr[b].add(a);
        }

        dfs(0, 0);

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

    private static void dfs(int start, int distance) {
        visit[start] = true;

        int changeCnt = 0;
        for (Integer adj: arr[start]) {
            if (!visit[adj]) {
                dfs(adj, distance+1);
                changeCnt++;
            }
        }

        if (changeCnt == 0) {
            diff += distance;
        }

        visit[start] = false;
    }
}

• 트리문제에 익숙하지 않아 계속 트리를 구성하려고 하다보니 시간이 많이 들었다 (+ 시간초과도 남)
• 사실 그냥 보면 dfs이다. 리프노드 찾고 그냥 깊이를 더하면 되는 문제였음
• 트리문제를 풀 때 트리자체를 구성하려는 강박을 안가져야겠다.

 

 

 

 

 

 

 

 

참고자료

https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14

트리(Tree)