트리

1. ㅇ롱클래스와 참조를 이용한 방식

각 노드를 객체로 만들고, 자식 노드를 참조(주소값)로 연결하는 형태입니다.

• 장점 :

  • 트리의 모양이나 크기에 제약이 없어 매우 유연함

  • 노드의 추가, 삭제가 비교적 자유롭다.

  • 재귀 함수를 사용한 순회(Traversal) 로직을 직관적으로 구현 할 수 있다.

Java

class TreeNode {
    int val; //노드의 값
    TreeNode left; // 왼쪽 자식 노드를 가리키는 참조
    TreeNode right; // 오른쪽 자식 노드를 가리키는 참조
    
    // 생성자
    TreeNode(int val) {
        this.val = val;
        }
    }
}

1. 배열/ArrayList를 이용한 방식

이 방식은 주로 완전 이진 트리(Complete Binary Tree)나 힙(Heap)과 같은 특정 형태의 트리를 표현할 때 매우 효율적입니다.

배열의 인덱스를 이용해 부모-자식 관계를 정의합니다.

• 인덱스 i에 있는 노드의:

  • 부모 노드 인덱스: (i - 1) / 2

  • 왼쪽 자식 노드 인덱스: 2 * i + 1

  • 오른쪽 자식 노드 인덱스: 2 * i + 2

• 장점:

  • 완전 이진 트리의 경우, 포인터 메모리 없이 데이터를 빽빽하게 저장할 수 있어 공간 효율이 좋습니다.

  • 인덱스 계산만으로 부모/자식 노드에 빠르게 접근할 수 있습니다.

• 단점:

  • 트리가 한쪽으로 치우치는 등 모양이 불규칙하면 사용하지 않는 인덱스가 많아져 심각한 공간 낭비가 발생합니다.

  • 노드의 추가, 삭제가 번거로울 수 있습니다.

배열로 표현한 이진 트리를 순회하는 코드

class Solution {
    public static String[] solution(int[] nodes) {
        String[] result = new String[3];
        result[0] = preorder(nodes, 0).trim();
        result[1] = inorder(nodes, 0).trim();
        result[2] = postorder(nodes, 0).trim();
        return result;
    }
    
    private static String preorder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }
        
        return nodes[idx] + "" + preorder(nodes, 2*idx + 1) +" " +
            preorder(nodes, 2*idx +2);
    }
    
    private static String inorder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }
        
        return inorder(nodes, 2*idx + 1) +" " + nodes[idx] + " " + 
            inorder(nodes, 2*idx +2);
    }
    
    private static String postorder(int[] nodes, int idx) {
        if (idx >= nodes.length) {
            return "";
        }
        
        return postorder(nodes, 2*idx + 1)  + " " + 
            postorder(nodes, 2*idx +2) + " " + nodes[idx];
    }
        

DFS(재귀(스택))을 이용한 순회

public static void preOrder(TreeNode node){
        // 재귀의 탈출 조건 : 방문한 노드가 null이면 즉시 종료
        if (node == null) return;

        // 1. Root : 현재 노드의 값을 먼저 처리
        System.out.print(node.value + " -> ");

        // 2. Left : 왼쪽 서브트리를 재귀적으로 순회
        preOrder(node.left);

        // 3. Right : 오른쪽 서버트리를 재귀적으로 순회
        preOrder(node.right);
    }

    public static void inOrder(TreeNode node){

        if(node == null) return;

        inOrder(node.left);
        
        System.out.print(node.value + " -> ");
        
        inOrder(node.right);

    }

    public static void postOrder(TreeNode node){
        if(node == null) return;

        postOrder(node.left);
        
        postOrder(node.right);
        
        System.out.print(node.value + " -> ");
    }
    

전위 : 트리 구성, 직렬화, 루트 우선 방문

중위 : BST 정렬/탐색 문제 -> BST를 중위 순회 하면 오름차순으로 정렬된 채로 출력됨.

후위 : 자식 먼저 처리해야 되는 문제 (트리 조건 확인, DP 삭제 등)

연습문제) 길찾기 게임

https://school.programmers.co.kr/learn/courses/30/lessons/42892

y,x 기반 정렬

-> tree 만들기

-> 전위, 후위 출력

BFS(너비 우선 탐색), 레벨 순서 순회(Level-order-traversal)

핵심 아이디어 : 큐(Queue)의 사용

1. 큐에 루트 노드를 넣는다.

2. 큐가 빌 때까지 다음을 반복한다.

   1. 큐에서 노드를 하나 꺼낸다 (Dequeue)

   2. 꺼낸 노드를 방문(처리)한다.

   3. 꺼낸 노드의 왼쪽 자식이 있다면 큐에 넣는다. (Enqueue)

   4. 꺼낸 노드의 오른쪽 자식이 있다면 큐에 넣는다. (Enqueue)

양 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/92343

제약 조건 : 내가 모은 양의 수보다 늑대의 수가 같거나 더 많으면 안됨.

탐색 방법 : 일반적인 트리 순회 (부모 -> 자식)과 다르다. 방문한 노드에 인접한 모든 노드가 다음 방문 대상 후보가 된다.

BFS 풀이

import java.util.*;
class Solution {

private static class Info {
    int node, sheep, wolf;
    HashSet<Integer> visited;
    
    public Info(int node, int sheep, int wolf, HashSet<Integer> visited) {
        this.node = node;
        this.sheep = sheep;
        this.wolf = wolf;
        this.visited = visited;
    }
}

private static ArrayList<Integer>[] tree; // 트리 정보를 저장할 인접 리스트

//1 트리 구축 메서드
private static void buildTree(int[] info, int[][] edges) {
    tree = new ArrayList[info.length];
    for (int i = 0; i < tree.length; i++) {
        tree[i] = new ArrayList<>();
    }
    
    for (int[] edge : edges) {
        tree[edge[0]].add(edge[1]);
    }
}

public int solution(int[] info, int[][] edges) {
    buildTree(info, edges);
    int answer = 0;
    
    //BFS를 위한 큐 생성 및 초기 상태 설정
    ArrayDeque<Info> queue = new ArrayDeque<>();
    queue.add(new Info(0,1,0,new HashSet<>()));
    
    //BFS 탐색 시작
    while(!queue.isEmpty()) {
        // 일단 큐에서 상태 꺼냄
        Info now = queue.poll();
        // 최대 양의 수 업뎃
        answer = Math.max(answer, now.sheep);
        // 방문한 노드 집합에 현재 노드의 이웃 노드 추가.
        now.visited.addAll(tree[now.node]);
        // 인접한 노드들에 대한 탐색
        for(int next : now.visited) {
            // 기존 해시셋의 데이터를 복사하고 현재 방문한 정점을 해시셋에서 제거
            HashSet<Integer> set = new HashSet<>(now.visited);
            set.remove(next);
            
            // 늑대일 경우
            if(info[next] == 1) {
                if(now.sheep > now.wolf + 1){
                    queue.add(new Info(next, now.sheep,now.wolf+1,set));
                }
            }//양일 경우
            else{
                queue.add(new Info(next, now.sheep+1,now.wolf,set));
            }
        }
    }
    
    return answer;
}
}

visited 집합이 각 Info 객체마다 독립적으로 관리된다.

now.visited.addAll(tree[now.node])를 통해 현재 노드의 이웃 노드들을 visited 집합에 추가하고 for(int next : now.visited) 루프를 통해 이 visited 집합의 모든 노드를 다음 탐색 대상으로 고려한다.

import java.util.*;

class Solution {
    // 각 노드의 자식 노드들을 저장할 인접 리스트
    List<Integer>[] adj;
    // 문제의 info 배열 (양/늑대 정보)
    int[] nodeInfo;
    // 최종적으로 찾은 양의 최대 마리 수
    int maxSheep = 0;
    
    public int solution(int[] info, int[][] edges) {
        this.nodeInfo = info;
        adj = new ArrayList[info.length];
        
        // 인접 리스트 초기화 및 그래프 구성
        for (int i = 0; i < info.length; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
        }
        
        // 초기 방문 가능한 노드 리스트 생성 
        List<Integer> reachableNodes = new ArrayList<>();
        reachableNodes.addAll(adj[0]);
        
        dfs(0,1,0,reachableNodes);
        
        return maxSheep;
    }
    
    private void dfs(int currentNode, int sheep, int wolf,List<Integer> reachableNodes) {
        maxSheep = Math.max(maxSheep,sheep);
        
        //현재 방문 가능한 노드들을 순회하며 다음 상태로 이동
        // 리스트를 순회하면서 요소를 변경하면 ConcurrentModification 발생하므로 복사본을 만들어 순회
        for(int nextNode : new ArrayList<>(reachableNodes)) {
            // 다음 노드로 이동했을 때의 양과 늑대의 수 계산
            int nextSheep = sheep + (nodeInfo[nextNode] == 0? 1 : 0);
            int nextWolf = wolf + (nodeInfo[nextNode] == 1? 1: 0);
            
            if(nextSheep <= nextWolf){
                continue;
            }
            
            List<Integer> newReachable = new ArrayList<>(reachableNodes);
            newReachable.remove(Integer.valueOf(nextNode));
            newReachable.addAll(adj[nextNode]);
            
            dfs(nextNode,nextSheep,nextWolf,newReachable);
        }
    }

}

표현 가능한 이진 트리 : https://school.programmers.co.kr/learn/courses/30/lessons/150367