[알고리즘] 이진 트리(백준 11725, 1911, 9934, 2263, 5639 -Java)

[알고리즘] 이진 트리(백준 11725, 1911, 9934, 2263, 5639)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

이진 트리

 

이진 트리는 각 노드의 자식 노드(차수)의 갯수가 2 이하로 구성된 트리를 의미 합니다.
트리 영역에서 가장 많이 사용되는 형태 입니다.^^
데이터의 탐색 속도를 빠르게 하기 위해 사용하는 구조 입니다.

1차원 배열로 표현할 수 있는 트리 입니다.

 

이진 트리 핵심 이론

이진 트리의 종류

데이터를 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 메모리가 낭비되는 단점이 존재합니다.
일반적으로 완전 이진 트리의 형태로 데이터를 담는 것을 추천 드립니다. 👍

 

이진 트리의 순차 표현
가장 직관적이면서 편리한 트리 자료구조 형태는 바로 배열 입니다.

 

Tree를 1차원 배열로 표현하면 다음과 같습니다.

 

⭐️ 1차원 배열의 형태로 표현할 때 트리의 노드와 배열의 인덱스 간의 상관 관계

• 루트 노드
  • index
• 부모 노드
  • index = index / 2
  • 단, 현재 노드가 루트 노드가 아님
• 왼쪽 자식 노드
  • index = index * 2
  • 단, index * 2 <= N(노드 갯수)
• 오른쪽 자식 노드
  • index = index * 2 + 1
  • 단, index * 2 + 1 <= N(노드 갯수)

 

이러한 연산 방식은 세그먼트 트리나 LCA 알고리즘에서도 기본적으로 사용하는 연산입니다.^^

 

전위 순회(preorder traversal)

0. 출발은 루트 노드
1. 현재 노드 방문
2. 재귀적으로 왼쪽 서브 트리 순회
3. 재귀적으로 오른쪽 트리 순회

 

 

중위 순회(inorder traversal)

이진 트리에서 주로 사용하는 순회 방법 입니다.
이진 트리에 있는 값을 순서대로 방문한다는 특징이 있습니다.

0. 출발은 루트 노드
1. 재귀적으로 왼쪽 서브 트리 순회
2. 현재 노드 방문
3. 재귀적으로 오른쪽 트리 순회

 

 

후위 순회(postorder traversal)

0. 출발은 루트 노드
1. 재귀적으로 왼쪽 서브 트리 순회
2. 재귀적으로 오른쪽 트리 순회
3. 현재 노드 방문

 

백준 11725

11725번: 트리의 부모 찾기

이 문제는 BFS를 이용하여 트리의 부모를 찾는 문제입니다.
트리를 어떻게 만들어야 하는지 고민을 많이 했습니다.
결국에 인접 리스트를 생성하여 문제를 해결했습니다.

 

 

풀이

public class Quiz11725 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 노드 갯수
        int n = Integer.parseInt(br.readLine());

        // 트리 초기화
        List<Integer>[] tree = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }

        // 트리 생성
        for(int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            // 양방향
            tree[node1].add(node2);
            tree[node2].add(node1);
        }

        // 트리의 루트는 1
        boolean[] visited = new boolean[n+1];
        // 부모노드를 담는 배열(index는 자식노드, 값은 부모노드)
        int[] parent = new int[n+1];

        // bfs 탐색 시작
        bfs(tree, visited, parent, 1);

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

        System.out.print(sb);
        br.close();
    }

    private static void bfs(List<Integer>[] tree, boolean[] visited, int[] parent, int start) {
        // bfs를 사용하여 루트 노드부터 탐색을 시작한다.
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();

            // 부모노드의 인접 노드(자식노드)
            for(Integer node : tree[poll]) {
                // 자식노드에 방문 이력이 없으면
                if(!visited[node]) {
                    visited[node] = true;
                    // 부모노드 저장
                    parent[node] = poll;
                    queue.offer(node);
                }
            }
        }
    }
}

백준 1991

1991번: 트리 순회

이 문제는 1차원 배열보다는 객체를 만들어서 해결하는 방법인것 같습니다.
이진트리를 처음 구현하는 저에게는 어려웠습니다. ㅠㅠ
백준 - Java 1991번 : 트리 순회

풀이

public class Quiz1991 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 노드 갯수
        int n = Integer.parseInt(br.readLine());

        // 이진 트리 생성
        Tree tree = new Tree();
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String parent = st.nextToken();
            String childL = st.nextToken();
            String childR = st.nextToken();

            // 트리 생성
            tree.createNode(parent, childL, childR);
        }

        StringBuilder sb = new StringBuilder();
        // 전위 순회(루트 -> 왼쪽 자식 -> 오른쪽 자식)
        tree.preOrder(tree.getRoot(), sb);
        sb.append("\n");
        // 중위 순회(왼쪽 자식 -> 루트 -> 오른쪽 자식)
        tree.inOrder(tree.getRoot(), sb);
        sb.append("\n");
        // 후위 순회(왼쪽 자식 -> 오른쪽 자식 -> 루트)
        tree.postOrder(tree.getRoot(), sb);

        System.out.print(sb);
        sb.setLength(0);
        br.close();
    }
    static class Node {
        private String data;
        private Node left;
        private Node right;

        public Node(String data) {
            this.data = data;
        }

        public String getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    static class Tree {
        private Node root;

        public Node getRoot() {
            return root;
        }

        public void createNode(String data, String leftData, String rightData) {
            // 루트 노드 이면
            if(root == null) {
                root = new Node(data);

                // 좌측에 값이 있는 경우
                if(!leftData.equals(".")); {
                    root.setLeft(new Node(leftData));
                }
                // 우측에 값이 있는 경우
                if(!rightData.equals(".")) {
                    root.setRight(new Node(rightData));
                }
            }
            // 루트 노드가 아니면
            else {
                // 어디에 노드가 들어가야할지 탐색한다.
                searchNode(root, data, leftData, rightData);
            }
        }

        private void searchNode(Node root, String data, String leftData, String rightData) {
            if(root == null) {
                return;
            }
            // 해당 노드에 탐색대상이 있으면
            else if(root.getData().equals(data)) {
                // 좌측에 값이 있는 경우
                if(!leftData.equals(".")) {
                    // 좌측에 저장
                    root.setLeft(new Node(leftData));
                }
                // 우측에 값이 있는 경우
                if(!rightData.equals(".")) {
                    // 우측에 저장
                    root.setRight(new Node(rightData));
                }
            } else {
                // 왼쪽으로 탐색
                searchNode(root.getLeft(), data, leftData, rightData);
                // 오른쪽으로 탐색
                searchNode(root.getRight(), data, leftData, rightData);
            }
        }

        public void preOrder(Node root, StringBuilder sb) {
            sb.append(root.getData());
            if(root.getLeft() != null) preOrder(root.getLeft(), sb);
            if(root.getRight() != null) preOrder(root.getRight(), sb);
        }

        public void inOrder(Node root, StringBuilder sb) {
            if(root.getLeft() != null) inOrder(root.getLeft(), sb);
            sb.append(root.getData());
            if(root.getRight() != null) inOrder(root.getRight(), sb);
        }

        public void postOrder(Node root, StringBuilder sb) {
            if(root.getLeft() != null) postOrder(root.getLeft(), sb);
            if(root.getRight() != null) postOrder(root.getRight(), sb);
            sb.append(root.getData());
        }
    }
}

백준 9934

9934번: 완전 이진 트리

트리에 대한 완전한 이해가 없어서 어려웠습니다. ㅠㅠ

이 문제를 풀기 위해서는
중위 순회에 대해서 알아야 합니다.
중위 순회는 항상 왼쪽 자식부터 순회 시작합니다.
(순회 순서: 왼쪽 자식 -> 루트 -> 오른쪽 자식)

완전 이진트리에서 중위 순회는 주어진 배열의 가운데가 항상 부모 노드입니다.
그리고 가운데를 기점으로 왼쪽, 오른쪽으로 탐색하면 됩니다.

 

풀이

public class Quiz9934 {
    static int k = 0;
    public static void main(String[] args) throws IOException {
        // 상근이가 중위 순회로 방문함
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());

        // 노드 갯수
        int nodeNum = (int) Math.pow(2, k) - 1;

        // 경로 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] path = new int[nodeNum];
        for(int i = 0; i < nodeNum; i++) {
            int node = Integer.parseInt(st.nextToken());
            path[i] = node;
        }

        // 지도 초기화
        List<Integer>[] map = new ArrayList[k];
        for(int i = 0; i < k; i++) {
            map[i] = new ArrayList<>();
        }

        // 지도 생성
        createMap(map, path, 0, 0, path.length - 1);

        // 지도 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < k; i++) {
            for(Integer building : map[i]) {
                sb.append(building).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
        sb.setLength(0);
        br.close();
    }

    private static void createMap(List<Integer>[] map, int[] path, int depth, int start, int end) {

        // 완전 이진트리이기 때문에 k 만큼의 깊이가 생김
        if(depth == k) return;

        // 상근이가 중위 순회로 방문(왼쪽 서브트리 순회 -> 현재 방문 -> 오른쪽 서브트리 순회)
        // 방문 배열의 중간이 부모 노드
        int mid = (start + end) / 2;
        // 경로 저장
        map[depth].add(path[mid]);

        // 왼쪽으로 탐색
        createMap(map, path, depth + 1, start, mid - 1);
        // 오른쪽으로 탐색
        createMap(map, path, depth + 1, mid + 1, end);
    }
}

백준 2263

2263번: 트리의 순회

너무 어려운 문제였습니다. 😭
이 문제는 중위, 후위, 전위 순회에 대한 지식이 필요합니다.
그리고 분할과 정복이라는 개념도 필요합니다.
추가로 메모리에 대한 것도 고려해야 해결할 수 있는 문제 입니다.
(아직도 너무 어렵습니다….😇)

 

필요 지식

• 이진트리의 중위, 후위, 전위 순회 개념
• 분할과 정복
• 메모리 고려

백준BOJ 2263번 트리의 순회.java
백준 2263 - 분할정복 - 트리의 순회(java) :: 팡스블로그

 

과정
대략적으로 이러한 과정을 반복합니다.

 

 

 

전체 과정

// 입력 데이터
6
4 2 5 1 3 6
4 5 2 6 3 1 

// 로그
inStart=1, inEnd=6, postStart=1, postEnd=6, 정지 여부=false
inStart=1, inEnd=3, postStart=1, postEnd=3, 정지 여부=false
inStart=1, inEnd=1, postStart=1, postEnd=1, 정지 여부=false
inStart=1, inEnd=0, postStart=1, postEnd=0, 정지 여부=true
inStart=2, inEnd=1, postStart=1, postEnd=0, 정지 여부=true
inStart=3, inEnd=3, postStart=2, postEnd=2, 정지 여부=false
inStart=3, inEnd=2, postStart=2, postEnd=1, 정지 여부=true
inStart=4, inEnd=3, postStart=2, postEnd=1, 정지 여부=true
inStart=5, inEnd=6, postStart=4, postEnd=5, 정지 여부=false
inStart=5, inEnd=4, postStart=4, postEnd=3, 정지 여부=true
inStart=6, inEnd=6, postStart=4, postEnd=4, 정지 여부=false
inStart=6, inEnd=5, postStart=4, postEnd=3, 정지 여부=true
inStart=7, inEnd=6, postStart=4, postEnd=3, 정지 여부=true

 

풀이

public class Quiz2263 {
    static StringBuilder sb = new StringBuilder();
    static int n;
    static int[] inorder;
    static int[] postorder;
    static int[] inorderIndex;
    public static void main(String[] args) throws IOException {
        // 중위 순회와, 후위 순회가 주어질 때 전위 순회를 출력
        // 중위 순회와 후위 순회를 이용하여 트리의 원형을 만들고 전위 순회를 출력 한다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 노드 갯수
        n = Integer.parseInt(br.readLine());

        // 중위 순회 저장
        inorder = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            inorder[i] = Integer.parseInt(st.nextToken());
        }

        // 후위 순회 저장
        postorder = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            postorder[i] = Integer.parseInt(st.nextToken());
        }

        // 중위 순회 노드의 인덱스를 저장하는 배열
        inorderIndex = new int[n+1];
        for(int i = 1; i <= n ; i++) {
            // 인덱스: 중위순회 노드, 값: 중위순회 인덱스
            inorderIndex[inorder[i]] = i;
        }

        createTree(1, inorder.length - 1, 1, postorder.length - 1);

        System.out.print(sb);
        br.close();
    }

    private static void createTree(int inStart, int inEnd, int postStart, int postEnd) {
        //System.out.println("inStart="+inStart+", inEnd="+inEnd+", postStart="+postStart+", postEnd="+postEnd +", 정지 여부="+(postStart > postEnd || inStart > inEnd));
        // 중위, 후위 순회의 시작점이 종료점 보다 크면
        if(postStart > postEnd || inStart > inEnd) return;

        int parent = postorder[postEnd];
        // 중위 순회의 부모노드 인덱스
        int parentIndex = inorderIndex[parent];

        // 출력
        sb.append(parent).append(" ");

        // 중위 순회에서 루트 기준 왼쪽에 몇개가 있는지 계산
        int leftSize = parentIndex - inStart;

        // 좌측 탐색
        // 좌측 배열 끝점 = postStart + leftSize - 1 = 후위순위 시작점 + 좌측 탐색 대상의 배열 길이 - 루트노드 길이
        createTree(inStart, parentIndex - 1, postStart, postStart + leftSize - 1);
        // 우측 탐색
        // 우측 배열 시작점 = postStart + leftSize = 후위 배열 시작점 + 좌측 탐색 대상의 배열 길이
        createTree(parentIndex + 1, inEnd, postStart + leftSize, postEnd - 1);

    }
}

백준 5639

5639번: 이진 검색 트리

다른 사람의 풀이를 통해 해결했습니다..
조건에 맞게 이진 트리를 만들고 후위 순회를 구현하는 문제 입니다.
(개인적으로 저는 재귀 함수를 사용하면 그 흐름을 잘 이해하기 어려운것 같습니다.. ㅠㅠ)

 

풀이

public class Quiz5639 {
    static StringBuilder sb =  new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 전위 순회
        int value = Integer.parseInt(br.readLine());
        Node node = new Node(value);

        while (true) {
            String str = br.readLine();
            if(str == null || str.equals("")) break;
            node.createNode(Integer.parseInt(str), node);
        }

        // 후위 순회
        node.getPostorder(node);

        System.out.println(sb);
    }

    static class Node {
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
        }

        public void createNode(int data, Node node) {
            // 왼쪽
            if(node.getData() > data) {
                if(node.getLeft() == null) {
                    node.setLeft(new Node(data));
                } else {
                    createNode(data, node.getLeft());
                }
            }
            // 오른쪽
            else {
                if(node.getRight() == null) {
                    node.setRight(new Node(data));
                } else {
                    createNode(data, node.getRight());
                }
            }
        }

        public void getPostorder(Node node) {
            // 후위순회: 왼쪽 -> 오른쪽 -> 루트
            if(node.getLeft() != null) node.getPostorder(node.getLeft());
            if(node.getRight() != null) node.getPostorder(node.getRight());
            sb.append(node.getData()).append("\n");
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }

}

정리

트리의 개념은 그렇게 어려운것 같지 않은데..
전반적으로 트리 문제가 어려운것 같습니다… ㅠㅠ

많이 연습해야겠네요 ㅠ0ㅠ

 

ㅎㅇㅌ....!!! 💪