[멋쟁이사자처럼 부트캠프 TIL] 유니티 게임 스쿨 3기 15일차

 

 

 

15일차 요약

트리

• 트리는 계층적 구조를 표현하는 비선형 자료구조
• 트리의 종류
  • 일반 트리: 노드가 임의의 수의 자식을 가질 수 있는 트리
  • 이진 트리: 각 노드가 최대 2개의 자식을 가질 수 있는 트리
  • 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
  • 포화 이진 트리: 모든 내부 노드가 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있는 트리
  • 이진 탐색 트리: 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리
  • AVL 트리: 자동으로 균형을 맞추는 이진 탐색 트리로, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1
  • 레드-블랙 트리: 자가 균형 이진 탐색 트리의 일종으로, 색상 속성을 사용하여 균형을 유지
  • B-트리: 데이터베이스와 파일 시스템에서 사용되는 균형 검색 트리로, 노드당 여러 개의 키를 저장

AVL 트리

• 자동으로 균형을 맞추는 트리
• 편향성 제거
• 추가적인 연산 필요

레드블랙 트리

• AVL트리 중 하나
• 특정 규칙에 의해 삽입, 삭제 연산
• 복잡한 회전 연산이 필요

 

그래프

• 노드들과 그들을 연결하는 간선들의 집합으로 이루어진 자료구조
• 사이클 가능
• 다양한 상황에 활용 가능
• 순회, 최단 경로 등 다양한 알고리즘이 있음

 

 

 

 

 

 

 

 

---

 

트리 (Tree)

트리는 계층적 구조를 표현하는 비선형 자료구조이다.

노드들과 간선들로 구성되어 있다.

 

트리의 주요 특징

• 하나의 루트 노드를 가진다.
• 각 노드는 0개 이상의 자식 노드를 가질 수 있다.
• 사이클이 존재하지 않는다.

 

트리의 종류

• 일반 트리 (General Tree): 노드가 임의의 수의 자식을 가질 수 있는 트리
• 이진 트리 (Binary Tree): 각 노드가 최대 2개의 자식을 가질 수 있는 트리
• 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
• 포화 이진 트리 (Perfect Binary Tree): 모든 내부 노드가 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있는 트리
• 이진 탐색 트리 (Binary Search Tree): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리
• AVL 트리: 자동으로 균형을 맞추는 이진 탐색 트리로, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1
• 레드-블랙 트리 (Red-Black Tree): 자가 균형 이진 탐색 트리의 일종으로, 색상 속성을 사용하여 균형을 유지
• B-트리: 데이터베이스와 파일 시스템에서 사용되는 균형 검색 트리로, 노드당 여러 개의 키를 저장

 

트리의 순회 방법

• 전위 순회 (Preorder): 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
• 중위 순회 (Inorder): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
• 후위 순회 (Postorder): 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
• 레벨 순회 (Level-order): 루트부터 레벨별로 왼쪽에서 오른쪽으로 순회

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class BinaryTree : MonoBehaviour
{
    public class Node
    {
        public int Data;
        public Node Left;
        public Node Right;

        public Node(int data)
        {
            Data = data;
            Left = Right = null;
        }
    }
        
    private Node root;

    // 전위 순회
    public void Preorder(Node node)
    {
        if (node == null) return;

        Debug.Log(node.Data + " "); // 루트
        Preorder(node.Left);        // 왼쪽 서브트리
        Preorder(node.Right);       // 오른쪽 서브트리
    }

    // 중위 순회
    public void Inorder(Node node)
    {
        if (node == null) return;

        Inorder(node.Left);         // 왼쪽 서브트리
        Debug.Log(node.Data + " "); // 루트
        Inorder(node.Right);        // 오른쪽 서브트리
    }

    // 후위 순회
    public void Postorder(Node node)
    {
        if (node == null) return;

        Postorder(node.Left);       // 왼쪽 서브트리
        Postorder(node.Right);      // 오른쪽 서브트리
        Debug.Log(node.Data + " "); // 루트
    }

    void Start()
    {
        root = new Node(100);
        root.Left = new Node(50);
        root.Left.Left = new Node(40);
        root.Left.Right = new Node(60);
        root.Right = new Node(110);
        
        /*
                100
            50      110 
         40     60
         */

        Debug.Log("전위 순회:");
        Preorder(root);
        
        Debug.Log("중위 순회:");
        Inorder(root);
        
        Debug.Log("후위 순회:");
        Postorder(root);
    }
}

---

 

 

 

 

 

그래프 (Graph)

그래프는 노드들과 그들을 연결하는 간선들의 집합으로 이루어진 자료구조이다.

트리와 달리 순환이 허용되며, 더 유연한 관계 표현이 가능하다.

 

그래프의 주요 특징

• 방향성: 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 구분
• 가중치: 간선에 비용이나 거리 등의 가중치를 부여할 수 있다.
• 순환성: 순환(Cycle)이 허용되어 한 노드에서 시작하여 같은 노드로 돌아올 수 있다.
• 연결성: 모든 노드가 연결되어 있지 않을 수 있다.

 

그래프의 구현 방법

• 인접 행렬 (Adjacency Matrix): 2차원 배열을 사용하여 노드 간의 연결 관계를 표현
• 인접 리스트 (Adjacency List): 각 노드마다 연결된 노드들의 리스트를 유지

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Graph : MonoBehaviour
{
    public class Vertex
    {
        public string name;
        public Dictionary<Vertex, int> neighbors = new Dictionary<Vertex, int>();

        public Vertex(string name)
        {
            this.name = name;
        }
    }

    private Dictionary<string, Vertex> Vertices = new Dictionary<string, Vertex>();

    public void AddVertex(string name)
    {
        if (Vertices.ContainsKey(name))
        {
            Vertices.Add(name, new Vertex(name));
        }
    }

    public void AddEdge(string from, string to, int weight)
    {
        if (Vertices.ContainsKey(from) && Vertices.ContainsKey(to))
        {
            Vertex fromV = Vertices[from];
            Vertex toV = Vertices[to];

            if (!fromV.neighbors.ContainsKey(toV))
            {
                fromV.neighbors.Add(toV, weight);
            }
        }
    }
    
    // 너비 우선 탐색 (BFS)
    public void BFS(string startName)
    {
        if (!Vertices.ContainsKey(startName)) return;

        HashSet<Vertex> visited = new HashSet<Vertex>();
        Queue<Vertex> queue = new Queue<Vertex>();
        
        Vertex start = Vertices[startName];
        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0)
        {
            Vertex current = queue.Dequeue();
            Debug.Log($"방문: {current.name}");

            foreach (var neighbor in current.neighbors.Keys)
            {
                if (!visited.Contains(neighbor))
                {
                    visited.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }
    }

    // 깊이 우선 탐색 (DFS)
    public void DFS(string startName)
    {
        if (!Vertices.ContainsKey(startName)) return;
        HashSet<Vertex> visited = new HashSet<Vertex>();
        DFSUtil(Vertices[startName], visited);
    }
    
    private void DFSUtil(Vertex vertex, HashSet<Vertex> visited)
    {
        visited.Add(vertex);
        Debug.Log($"방문: {vertex.name}");

        foreach (var neighbor in vertex.neighbors.Keys)
        {
            if (!visited.Contains(neighbor))
            {
                DFSUtil(neighbor, visited);
            }
        }
    }
    
        // 다익스트라 최단 경로 알고리즘
    public void Dijkstra(string startName)
    {
        if (!Vertices.ContainsKey(startName)) return;

        Dictionary<Vertex, float> distances = new Dictionary<Vertex, float>();
        Dictionary<Vertex, Vertex> previous = new Dictionary<Vertex, Vertex>();
        HashSet<Vertex> unvisited = new HashSet<Vertex>();
        
        // 초기화
        foreach (var vertex in Vertices.Values)
        {
            distances[vertex] = float.MaxValue;
            previous[vertex] = null;
            unvisited.Add(vertex);
        }

        Vertex start = Vertices[startName];
        distances[start] = 0;

        while (unvisited.Count > 0)
        {
            // 가장 가까운 미방문 정점 찾기
            Vertex current = null;
            float minDistance = float.MaxValue;
            foreach (var vertex in unvisited)
            {
                if (distances[vertex] < minDistance)
                {
                    current = vertex;
                    minDistance = distances[vertex];
                }
            }

            if (current == null) break;

            unvisited.Remove(current);

            foreach (var neighbor in current.neighbors)
            {
                float alt = distances[current] + neighbor.Value;
                if (alt < distances[neighbor.Key])
                {
                    distances[neighbor.Key] = alt;
                    previous[neighbor.Key] = current;
                }
            }
        }

        // 결과 출력
        foreach (var vertex in Vertices.Values)
        {
            Debug.Log($"{startName}에서 {vertex.name}까지의 최단 거리: {distances[vertex]}");
        }
    }
    
    void Start()
    {
        AddVertex("A");
        AddVertex("B");
        AddVertex("C");
        AddVertex("D");
        
        AddEdge("A", "B", 1);
        AddEdge("B", "C", 1);
        AddEdge("C", "D", 1);
        AddEdge("D", "A", 1);
        
        BFS("A");
        DFS("A");
    }
}

 

 

그래프의 주요 알고리즘

• 깊이 우선 탐색 (DFS): 한 방향으로 깊이 탐색하다가 더 이상 갈 수 없으면 백트래킹
• 너비 우선 탐색 (BFS): 현재 노드와 가까운 노드부터 탐색
• 다익스트라 알고리즘: 가중 그래프에서 최단 경로를 찾는 알고리즘 중 하나
• 크루스칼 알고리즘: 최소 신장 트리를 찾는 알고리즘 중 하나

---

 

 

 

 

 

AVL 트리

이진트리의 편향성을 제거하기 위해 균형을 맞추는 트리이다.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AVLTreeVisualizer : MonoBehaviour
{
    private class Node
    {
        public int data;
        public Node left;
        public Node right;
        public int height;
        public Vector2 position;

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

    private Node root;

    void Start()
    {
        for (int i = 1; i <= 9; i++)
        {
            Insert(i);
        }
        UpdatePositions(root, 0, 0, 2);
    }

    // Insert function
    public void Insert(int data)
    {
        root = InsertRec(root, data);
    }

    private Node InsertRec(Node node, int data)
    {
        if (node == null) return new Node(data);

        if (data < node.data)
        {
            node.right = InsertRec(node.right, data);
        }
        else if (data > node.data)
        {
            node.right = InsertRec(node.right, data);
        }
        else
        {
            return node;
        }

        UpdateHeight(node);
        return Balance(node, data);
    }

    private int Height(Node node)
    {
        return node == null ? 0 : node.height;
    }

    private int GetBalance(Node node)
    {
        return node == null ? 0 : Height(node.left) - Height(node.right);
    }

    private void UpdateHeight(Node node)
    {
        if (node != null)
        {
            node.height = Mathf.Max(Height(node.left), Height(node.right)) + 1;
        }
    }

    private Node RightRotate(Node y)
    {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        UpdateHeight(y);
        UpdateHeight(x);

        return x;
    }

    private Node LeftRotate(Node x)
    {
        Node y = x.right;
        Node T2 = y.left;
        
        y.left = x;
        x.right = T2;

        UpdateHeight(x);
        UpdateHeight(y);

        return y;
    }

    private Node Balance(Node node, int data)
    {
        int balance = GetBalance(node);

        //left > right
        if (balance > 1 && data < node.left.data)
        {
            return RightRotate(node);
        }

        //left < right
        if (balance < -1 && data > node.right.data)
        {
            return LeftRotate(node);
        }

        //left > right
        if (balance > 1 && data > node.left.data)
        {
            node.left = LeftRotate(node.left);
            return RightRotate(node);
        }
        
        //left < right
        if (balance < -1 && data < node.right.data)
        {
            node.right = RightRotate(node.right);
            return LeftRotate(node);
        }

        return node;
    }

    private void UpdatePositions(Node node, float x, float y, float horizontalSpacing)
    {
        if (node == null) return;

        node.position = new Vector2(x, y);

        UpdatePositions(node.left, x - horizontalSpacing, y - 1.5f, horizontalSpacing / 2);
        UpdatePositions(node.right, x + horizontalSpacing, y - 1.5f, horizontalSpacing / 2);
    }

    private void OnDrawGizmos()
    {
        if (root != null)
        {
            DrawNode(root);
        }
    }

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

        // Draw connections to children
        if (node.left != null)
        {
            Gizmos.color = Color.white;
            Gizmos.DrawLine(new Vector3(node.position.x, node.position.y, 0), 
                            new Vector3(node.left.position.x, node.left.position.y, 0));
        }

        if (node.right != null)
        {
            Gizmos.color = Color.white;
            Gizmos.DrawLine(new Vector3(node.position.x, node.position.y, 0), 
                            new Vector3(node.right.position.x, node.right.position.y, 0));
        }

        // Draw the node
        Gizmos.color = Color.cyan;
        Gizmos.DrawSphere(new Vector3(node.position.x, node.position.y, 0), 0.2f);

        // Draw node label
        UnityEditor.Handles.Label(new Vector3(node.position.x, node.position.y + 0.3f, 0), 
                                  $"   {node.data} (h:{node.height})");

        // Recursively draw children
        DrawNode(node.left);
        DrawNode(node.right);
    }
}

주요 함수는 Rotate함수이다.

• LeftRotate: 노드를 왼쪽으로 회전시킨다.
  • 오른쪽 자식이 자신의 위치로 이동하며, 자신은 오른쪽 자식의 왼쪽 자식이 된다.
  • 또한, 오른쪽 자식의 왼쪽 자식이 자신의 오른쪽 자식이 된다. (자신보다 크기 때문)
• RightRotate: 노드를 오른쪽으로 회전시킨다.
  • 왼쪽 자식이 자신의 위치로 이동하며, 자신은 왼쪽 자식의 오른쪽 자식이 된다.
  • 또한, 왼쪽 자식의 오른쪽 자식은 자신의 왼쪽 자식이 된다.(자신보다 작기 때문)

---

 

 

레드 블랙 트리 (RB Tree)

레드-블랙 트리는 자가 균형 이진 탐색 트리의 일종으로, 다음과 같은 특성을 가진다.

• 모든 노드는 빨간색 또는 검은색
• 루트 노드는 검은색
• 모든 리프(NIL) 노드는 검은색
• 빨간색 노드의 자식은 모두 검은색
• 모든 노드에 대해, 그 노드로부터 리프 노드까지의 경로는 모두 같은 수의 검은색 노드를 포함

 

using UnityEngine;

public class RedBlackTree : MonoBehaviour
{
    // 노드의 색상을 정의하는 열거형
    private enum NodeColor
    {
        Red,
        Black
    }

    // 노드 클래스 정의
    private class Node
    {
        public int data;
        public Node left, right, parent;
        public NodeColor color;

        // 새로운 노드는 항상 Red로 생성 (조건 1 관련)
        public Node(int data)
        {
            this.data = data;
            left = right = parent = null;
            color = NodeColor.Red;
        }
    }

    private Node root;
    private Node TNULL; // NIL 노드 (조건 3 관련)

    void Start()
    {
        // NIL 노드는 항상 Black (조건 3)
        TNULL = new Node(0);
        TNULL.color = NodeColor.Black;
        root = TNULL;
    }

    // 삽입 시 트리 재조정을 위한 좌회전
    private void LeftRotate(Node x)
    {
        Node y = x.right;
        x.right = y.left;
        
        if (y.left != TNULL)
            y.left.parent = x;
            
        y.parent = x.parent;
        
        if (x.parent == null)
            root = y;
        else if (x == x.parent.left)
            x.parent.left = y;
        else
            x.parent.right = y;
            
        y.left = x;
        x.parent = y;
    }

    // 삽입 시 트리 재조정을 위한 우회전
    private void RightRotate(Node x)
    {
        Node y = x.left;
        x.left = y.right;
        
        if (y.right != TNULL)
            y.right.parent = x;
            
        y.parent = x.parent;
        
        if (x.parent == null)
            root = y;
        else if (x == x.parent.right)
            x.parent.right = y;
        else
            x.parent.left = y;
            
        y.right = x;
        x.parent = y;
    }

    // 노드 삽입
    public void Insert(int key)
    {
        Node node = new Node(key);
        node.left = TNULL;
        node.right = TNULL;

        Node y = null;
        Node x = root;

        // 삽입 위치 찾기
        while (x != TNULL)
        {
            y = x;
            if (node.data < x.data)
                x = x.left;
            else
                x = x.right;
        }

        node.parent = y;
        
        if (y == null)
            root = node;  // 조건 2: 루트는 항상 Black이 되도록 InsertFixup에서 처리
        else if (node.data < y.data)
            y.left = node;
        else
            y.right = node;

        InsertFixup(node); // 레드-블랙 트리 속성 복구
    }

    // 삽입 후 레드-블랙 트리 속성 복구
    private void InsertFixup(Node k)
    {
        Node u;
        // 조건 4: Red 노드의 자식은 Black이어야 함
        while (k.parent != null && k.parent.color == NodeColor.Red)
        {
            if (k.parent == k.parent.parent.right)
            {
                u = k.parent.parent.left;
                // Case 1: 삼촌 노드가 Red인 경우
                if (u.color == NodeColor.Red)
                {
                    // 색상 변경으로 해결
                    u.color = NodeColor.Black;
                    k.parent.color = NodeColor.Black;
                    k.parent.parent.color = NodeColor.Red;
                    k = k.parent.parent;
                }
                else
                {
                    // Case 2 & 3: 삼촌 노드가 Black인 경우
                    if (k == k.parent.left)
                    {
                        k = k.parent;
                        RightRotate(k);
                    }
                    // 색상 변경 및 회전으로 해결
                    k.parent.color = NodeColor.Black;
                    k.parent.parent.color = NodeColor.Red;
                    LeftRotate(k.parent.parent);
                }
            }
            else
            {
                // 위의 경우의 대칭
                u = k.parent.parent.right;
                if (u.color == NodeColor.Red)
                {
                    u.color = NodeColor.Black;
                    k.parent.color = NodeColor.Black;
                    k.parent.parent.color = NodeColor.Red;
                    k = k.parent.parent;
                }
                else
                {
                    if (k == k.parent.right)
                    {
                        k = k.parent;
                        LeftRotate(k);
                    }
                    k.parent.color = NodeColor.Black;
                    k.parent.parent.color = NodeColor.Red;
                    RightRotate(k.parent.parent);
                }
            }
            if (k == root)
                break;
        }
        // 조건 2: 루트는 항상 Black
        root.color = NodeColor.Black;
    }
}

---