[멋쟁이사자처럼 부트캠프 TIL 회고] Unity 게임 개발 3기 15일차

 

목차

---

자료구조

Tree

: 계층적 구조를 표현하는 비선형 자료구조 --> 노드와 노드를 연결하는 간선으로 구성

※ 이때까지 배운 자료구조 (Array, LinkedList, Stack, Queue)는 선형적인 자료구조

 

특징

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

용어

• 노드(Node) : 트리를 구성하는 기본요소로, 데이터를 저장한다.
• 간선(Edge) : 노드와 노드를 연결하는 선
• 루트 노드(Root Node) : 트리의 최상위에 있는 노드
• 부모 노드(Parent Node) : 직접적인 상위 노드
• 자식 노드(Child Node) : 직접적인 하위 노드
• 리프 노드(Leaf Node) : 자식이 없는 노드로, 트리의 끝단에 위치
• 깊이 (Depth) : 루트에서 특정 노드까지의 경로 길이
• 높이 (Height) : 노드에서 가장 먼 리프까지의 경로 길이

종류

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

※ 완전 이진 트리와 포화 이진 트리를 구분하는 것은 중요하지 않다. 개념만 알아두자

※ 편향된 트리(한 쪽 방향으로만 뻗어나가는 트리)가 생기면 차라리 배열을 쓰는게 낫다 --> 편향된 트리를 보완하기 위해 나온 것이 AVL 트리와 레드-블랙 트리다.

레드-블랙 트리의 특성

• 모든 노드는 빨간색 또는 검은색이다.
• 루트 노드는 검은색이다.
• 모든 리프(NIL) 노드는 검은색이다. --> NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드
• 빨간색 노드의 자식은 모두 검은색이다. --> 빨간색 노드가 연속으로 나올 수 없다.
• 모든 노드에 대해, 그 노드로부터 리프 노드까지의 경로는 모두 같은 수의 검은색 노드를 포함한다.

>> 레드-블랙 트리 쉽게 이해하기

https://code-lab1.com/red-black-tree/

[자료구조] 레드-블랙 트리(Red-Black Tree)란? 레드-블랙 트리 쉽게 이해하기 - 코드 연구소

Tree의 순회 방법

• 전위 순회(Preorder) : 루트 --> 왼쪽 서브트리 --> 오른쪽 서브트리
• 중위 순회(Inorder) : 왼쪽 서브트리 --> 루트 --> 오른쪽 서브트리
• 후위 순회(Postorder) : 왼쪽 서브트리 --> 오른쪽 서브트리 --> 루트
• 레벨 순회(Level-order) : 루트부터 레벨 별로 왼쪽에서 오른쪽으로 순회 --> 잘 사용되지 않는다.

각 순회 방법의 특징

• 전위 순회 : GameObject의 복사나 직렬화에 유용
• 중위 순회 : 이진 검색 트리에서 정렬된 순서로 노드를 방문할 때 사용
• 후위 순회 : GameObject의 삭제나 메모리 해제 시 유용
• 레벨 순회 : UI 요소의 계층적 렌더링이나 게임 로직의 단계별 처리에 적합

Tree 구현해보기

└ 이진 트리와 순회 방법 구현

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);
    }

    public void LevelOrder() // 레벨 순회
    {
        if (_root == null)
            return;

        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(_root);

        while (queue.Count > 0)
        {
            Node current = queue.Dequeue();
            Debug.Log(current.Data);
            
            if (current.Left != null)
                queue.Enqueue(current.Left);
            if (current.Right != null)
                queue.Enqueue(current.Right);
        }
    }

    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);
        
        //PreOrder(_root);
        InOrder(_root);
        //PostOrder(_root);
        //LevelOrder();
    }
}

※ 연산자 우선순위 --> Left = Right = null;

※ 재귀함수

└ AVL 트리 구현 (Unity)

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.left = InsertRec(node.left, 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);

        if (balance > 1 && data < node.left.data)
            return RightRotate(node);

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

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

        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);
    }
}

└ 레드-블랙 트리 구현

>> 이 구현에서 중요한 점

• 모든 새로운 노드는 Red로 삽입 (조건 1)
• 루트 노드는 항상 Black으로 유지 (조건 2)
• NIL 노드는 Black으로 처리 (조건 3)
• Red 노드의 자식들은 Black이 되도록 보장 (조건 4)
• 모든 경로의 Black 높이가 같도록 유지된다. (조건 5)

 

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;
    }
}

※ 레드-블랙 트리 시뮬레이터

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

---

Graph

: 노드(정점)와 이를 연결하는 간선의 집합으로 이루어진 자료구조

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

 

특징

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

주요 알고리즘

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

Unity에서의 Graph 활용

• 게임 맵 구현 : 이동 가능한 지점들을 노드로, 경로를 간선으로 표현
• AI 경로 찾기 : A* 알고리즘 등을 사용한 내비게이션 시스템 구현에 활용
• 소셜 네트워크 : 플레이어 간의 관계나 상호작용을 표현 가능
• 퀘스트 시스템 : 퀘스트 간의 의존성이나 진행 경로를 표현 가능

>> Graph는 복잡한 관계와 네트워크를 표현하는 데 매우 유용한 자료구조이며, 게임 개발에서 다양한 시스템을 구현하는 데 활용된다.

 

※ Graph 설명 유튜브 추천

https://www.youtube.com/watch?v=fVcKN42YXXI&t=33s

※ 최단경로 알고리즘 유튜브 추천

https://www.youtube.com/watch?v=tZu4x5825LI&t=214s

Graph 구현해보기

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

public class Graph : MonoBehaviour
{
    private void Start()
    {
        AddVertex("집");
        AddVertex("미용실");
        AddVertex("슈퍼마켓");
        AddVertex("영어학원");
        AddVertex("레스토랑");
        AddVertex("은행");
        AddVertex("학교");
            
        AddEdge("집", "미용실", 5.0f);
        AddEdge("집", "슈퍼마켓", 10.0f);
        AddEdge("집", "영어학원", 9.0f);
            
        AddEdge("미용실", "슈퍼마켓", 3.0f);
        AddEdge("미용실", "은행", 11.0f);
            
        AddEdge("슈퍼마켓", "레스토랑", 3.0f);
        AddEdge("슈퍼마켓", "영어학원", 7.0f);
        AddEdge("슈퍼마켓", "은행", 10.0f);
            
        AddEdge("영어학원", "은행", 7.0f);
        AddEdge("영어학원", "학교", 12.0f);
            
        AddEdge("레스토랑", "은행", 4.0f);
            
        AddEdge("은행", "학교", 2.0f);
            
        Debug.Log("DFS");
        DFS("집");
            
        Debug.Log("BFS");
        BFS("집");
            
        Debug.Log("Dijkstra");
        Dijkstra("집");
    }

    public class Vertex
    {
        public string Name;
        public Dictionary<Vertex, float> Neighbors = new Dictionary<Vertex, float>();

        public Vertex(string name)
        {
            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));
            Debug.Log($"정점 {name}이(가) 추가되었습니다.");
        }
    }

    public void AddEdge(string from, string to, float 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);
                Debug.Log($"간선 {from} --> {to} (가중치 : {weight}가 추가되었습니다.)");
            }
        }
    }

    public void BFS(string start) // 너비 우선 탐색(BFS)
    {
        if (!_vertices.ContainsKey(start))
            return;

        HashSet<Vertex> visited = new HashSet<Vertex>();
        Queue<Vertex> queue = new Queue<Vertex>();

        Vertex startV = _vertices[start];
        queue.Enqueue(startV);
        visited.Add(startV);

        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);
                }
            }
        }
    }

    public void DFS(string start)
    {
        if (!_vertices.ContainsKey(start))
            return;

        HashSet<Vertex> visited = new HashSet<Vertex>();
        DFSUtil(_vertices[start], 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 start)
    {
        if (!_vertices.ContainsKey(start))
            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 startV = _vertices[start];
        distances[startV] = 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($"{start}에서 {vertex.Name}까지의 최단 거리 : {distances[vertex]}");
        }
    }
}

└ Dictionary

: Index를 대신해 사용하는 Key와 Value 값이 세트로 이루는 배열

>> 가변적으로 크기 변경이 가능하며 key를 통해 접근 가능

>> Dictionary<키 자료형, 값 자료형> 이름 = new Dictionary<키 자료형, 값 자료형>();

기능

• Add(Key, Value) : Dictionary에 키와 값을 추가
• Remove(Key) : Dictionary에 해당하는 데이터 삭제
• Clear() : Dictionary에 저장된 모든 정보를 삭제
• Count : Dictionary의 모든 정보 개수를 조회
• ContainsKey(Key) : Dictionary안에 해당 키가 있는지 조회 --> 있으면 True, 없으면 False 반환
• ContainsValue(Value) : Dictionary안에 해당 값이 있는지 조회 --> 있으면 True, 없으면 False 반환
• OrderBy(i => i.Key) : 오름차순 정렬
• OrderByDescending(i => i.Key) : 내림차순 정렬

└ HashSet

: 해시 테이블을 기반으로 구현된 집합의 자료구조

>> 중복되지 않은 요소들의 모임을 관리하는데 최적화

>> 빠른 탐색과 무가 및 삭제 작업을 제공한다.

기능

• Add(item) : HashSet에 해당 요소를 추가 --> 요소가 이미 존재하면 추가되지 않으며, False를 반환
• Remove(item) : HashSet에 해당 요소를 삭제 --> 삭제에 성공하면 True, 실패하면 False를 반환
• Contains(item) : HashSet에 해당 요소가 포함되어 있는지 확인 --> 해당 요소가 존재하면 True를 반환
• Clear() : HashSet의 모든 요소를 제거
• Count : HashSet에 포함된 모든 요소의 수를 반환