[멋쟁이사자처럼부트캠프] 유니티 게임 개발 5기(39일차) - 재귀 및 알고리즘 (2)

✅ 오늘의 학습 목표
1. 재귀를 활용한 하노이 타워 클리어
2. 알고리즘 (2)

 

1. Hanoi Tower → 재귀 활용

하노이 타워는 반복 구조가 너무 뚜렷해서 재귀로 풀면 쉽게 클리어할 수 있다.

public class HanoiTower : MonoBehaviour
{
    public HanoiLevel hanoiLevel = HanoiLevel.Lv1;

    public Button answerButton;

    void Awake()
    {
        answerButton.onClick.AddListener(HanoiAnswer);
    }

    public void HanoiAnswer()
    {
        HanoiRoutine((int)hanoiLevel, 0, 1, 2);
    }

    private void HanoiRoutine(int n, int from, int temp, int to) // 기둥 0의 도넛 개수, 출발지, 임시처, 도착지
    {
        if (n == 1)
            Debug.Log($"{n}번 도넛을 {from}에서 {to}로 이동");
        else
        {
            HanoiRoutine(n - 1, from, to, temp);
            Debug.Log($"{n}번 도넛을 {from}에서 {to}로 이동");

            HanoiRoutine(n - 1, temp, from, to);
        }
    }
}

Lv1 기준

 

이렇게 큰 도넛 하나를 옮기기 위해 작은 도넛들을 임시 장소로 재귀적으로 이동시키고 마지막에 다시 합친다.

 

 

2. 알고리즘

1. 순차 탐색 (Linear Search)

배열을 순차적으로 탐색 O(n)

앞에서부터 하나하나 비교하면서 원하는 값을 찾는다.

using UnityEngine;

public class LinearSearch : MonoBehaviour
{
    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    public int target = 7;

    void Start()
    {
        LSearch(array, target);
    }

    private void LSearch(int[] arr, int t)
    {
        for (int i = 0; i < arr.Length; i++)
            if (arr[i] == t)
            {
                Debug.Log($"타겟 {t}은 {i}번째에 있습니다.");
                break;
            }
    }
}

 

순차 탐색은 배열 안에 모든 값을 비교하기 때문에 최악의 시간 복잡도 O(n)이 소요된다.

 

2. 이진 탐색 (Binary Search)

중간값을 기준으로 반씩 줄어들면서 탐색 O(logn)

using UnityEngine;

public class BinarySearch : MonoBehaviour
{
    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 정렬된 데이터만 탐색 가능
    private int target = 7;

    void Start()
    {
        int result = BSearch(); // Target의 인덱스 값
        Debug.Log(result);
    }

    private int BSearch()
    {
        int left = 0; // 처음 Left
        int right = array.Length - 1; // 처음 Right

        while (left <= right)
        {
            int mid = (left + right) / 2;

            if (array[mid] == target)
                return mid;
            else if (array[mid] < target)
                left = mid + 1;
            else // array[mid] > target
                right = mid - 1;
        }

        return -1;
    }
}

 

3. 이진 탐색 트리 (Binary Search Tree)

이진트리 기반으로 삽입/탐색하는 알고리즘 O(logn)

• PreOrder : Node → Left → Right  
• InOrder  : Left → Node → Right 
• PostOrder: Left → Right → Node

using System;
using UnityEngine;

public class BinarySearchTree : MonoBehaviour
{
    public class TreeNode
    {
        public TreeNode left;
        public TreeNode right;
        public int value;

        public TreeNode(int value)
        {
            this.value = value;
        }
    }

    private TreeNode root;
    private int[] array = { 8, 3, 10, 1, 6, 14, 4, 7, 13 }; // 배열

    private string result;

    void Start()
    {
        foreach (var v in array)
            root = Insert(root, v);

        PreOrder(root);
        Debug.Log($"PreOrder : {result.TrimEnd(',')}");

        result = String.Empty;
        InOrder(root);
        Debug.Log($"InOrder : {result.TrimEnd(',')}");

        result = String.Empty;
        PostOrder(root);
        Debug.Log($"PostOrder : {result.TrimEnd(',')}");
    }

    private TreeNode Insert(TreeNode node, int v)
    {
        if (node == null)
            return new TreeNode(v);

        if (v < node.value)
            node.left = Insert(node.left, v);
        else
            node.right = Insert(node.right, v);

        return node;
    }

    private void PreOrder(TreeNode node) // 전위 순회
    {
        if (node == null)
            return;

        result += $"{node.value}, ";
        PreOrder(node.left);
        PreOrder(node.right);
    }

    private void InOrder(TreeNode node) // 중위 순회
    {
        if (node == null)
            return;

        InOrder(node.left);
        result += $"{node.value}, ";
        InOrder(node.right);
    }

    private void PostOrder(TreeNode node) // 후위 순회
    {
        if (node == null)
            return;

        PostOrder(node.left);
        PostOrder(node.right);
        result += $"{node.value}, ";
    }
}

 

 

4. 깊이 우선 탐색 (Depth First Search)

한 노드를 끝까지 파고드는 탐색

using System.Collections.Generic;
using UnityEngine;

public class DepthFirstSearch : MonoBehaviour
{
    private int[,] nodes = new int[8, 8]
    {
      // 0  1  2  3  4  5  6  7
        {0, 1, 1, 1, 0, 0, 0, 0}, // 0
        {1, 0, 0, 0, 1, 1, 0, 0}, // 1
        {1, 0, 0, 0, 0, 0, 0, 0}, // 2
        {1, 0, 0, 0, 0, 0, 1, 0}, // 3
        {0, 1, 0, 0, 0, 1, 0, 0}, // 4
        {0, 1, 0, 0, 1, 0, 0, 1}, // 5
        {0, 0, 0, 1, 0, 0, 0, 0}, // 6
        {0, 0, 0, 0, 0, 1, 0, 0}, // 7
    };

    public Stack<int> stack = new Stack<int>();
    private bool[] visited = new bool[8];

    void Start()
    {
        DFSearch(0);
    }

    private void DFSearch(int start)
    {
        stack.Push(start);

        while (stack.Count > 0)
        {
            int index = stack.Pop();

            if (!visited[index]) // 방문 했는지 안했는지
            {
                visited[index] = true; // 방문 했다고 설정
                Debug.Log($"{index}번 노드에 방문");

                for (int i = nodes.GetLength(0) - 1; i >= 0; i--)
                {
                    if (nodes[index, i] == 1 && !visited[i])
                        stack.Push(i);
                }
            }
        }
    }
}

 

 

5. 너비 우선 탐색 (Breadth First Search)

한 레벨씩 옆으로 퍼지듯이 탐색

가까운 노드부터 방문하기 때문에 최단 거리 탐색에 자주 쓰인다.

using System.Collections.Generic;
using UnityEngine;

public class BreadthFirstSearch : MonoBehaviour
{
    private int[,] nodes = new int[8, 8]
    {
        // 0  1  2  3  4  5  6  7
        {0, 1, 1, 1, 0, 0, 0, 0}, // 0
        {1, 0, 0, 0, 1, 1, 0, 0}, // 1
        {1, 0, 0, 0, 0, 0, 0, 0}, // 2
        {1, 0, 0, 0, 0, 0, 1, 0}, // 3
        {0, 1, 0, 0, 0, 1, 0, 0}, // 4
        {0, 1, 0, 0, 1, 0, 0, 1}, // 5
        {0, 0, 0, 1, 0, 0, 0, 0}, // 6
        {0, 0, 0, 0, 0, 1, 0, 0}, // 7
    };

    public Queue<int> queue = new Queue<int>();
    private bool[] visited = new bool[8];

    void Start()
    {
        DFSearch(0);
    }

    private void DFSearch(int start)
    {
        queue.Enqueue(start);

        while (queue.Count > 0)
        {
            int index = queue.Dequeue();

            if (!visited[index]) // 방문 했는지 안했는지
            {
                visited[index] = true; // 방문 했다고 설정
                Debug.Log($"{index}번 노드에 방문");

                for (int i = 0; i < nodes.GetLength(0); i++)
                {
                    if (nodes[index, i] == 1 && !visited[i])
                        queue.Enqueue(i);
                }
            }
        }
    }
}