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

✅ 오늘의 학습 목표
1. 알고리즘 (3)

 

1. 알고리즘

1. 다익스트라 (Dijkstra)

효율적으로 최단거리를 찾을 수 있는 알고리즘

using UnityEngine;

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

    void Start()
    {
        int start = 0;
        int[] dist;
        int[] prev;

        Dijkstra(start, out dist, out prev);

        for (int i = 0; i < nodes.GetLength(0); i++)
            Debug.Log($"{start}에서 {i}까지 최단 거리 : {dist[i]}, 경로 : {GetPath(i, prev)}");
    }

    private void Dijkstra(int start, out int[] dist, out int[] prev)
    {
        int n = nodes.GetLength(0); // 6
        dist = new int[n];
        prev = new int[n];
        bool[] visited = new bool[n];

        // 지역 변수 값들을 초기화
        for (int i = 0; i < n; i++)
        {
            dist[i] = int.MaxValue; // 2,147,483,647
            prev[i] = -1;
            visited[i] = false;
        }

        dist[start] = 0; // 0번 노드에서 시작
        for (int cnt = 0; cnt < n; cnt++)
        {
            int u = -1;  // 최단 거리 노드
            int min = int.MaxValue; // 최단 거리

            // 방문하지 않은 노드 중 최단 거리 노드와 최단 거리 선택
            for (int j = 0; j < n; j++)
            {
                if (!visited[j] && dist[j] < min)
                {
                    min = dist[j];
                    u = j;
                }
            }

            if (u == -1) // 더이상 최단 거리 노드 없음
                break;

            visited[u] = true;

            for (int k = 0; k < n; k++)
            {
                if (nodes[u, k] > 0 && !visited[k])
                {
                    int newDist = dist[u] + nodes[u, k];
                    if (newDist < dist[k])
                    {
                        dist[k] = newDist;
                        prev[k] = u;
                    }
                }
            }
        }
    }

    private string GetPath(int end, int[] prev)
    {
        if (prev[end] == -1)
            return end.ToString();

        return $"{GetPath(prev[end], prev)} -> {end.ToString()}";
    }
}

 

 

2. 정렬 알고리즘

1. 선택 정렬 (Selection Sort)

가장 작은 값을 선택해서 앞으로 보내는 정렬

using UnityEngine;

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

    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Selection(array);
        Debug.Log("정렬 후 : " + string.Join (", ", array));
    }

    private void Selection(int[] array)
    {
        int n = array.Length;

        for (int i = 0; i < n - 1; i++) // i 인덱스 선택
        {
            int minIdx = i;

            for (int j = i + 1; j < n; j++) // 다음 인덱스(j)와 값 비교
            {
                if (array[j] < array[minIdx])
                    minIdx = j;
            }

            int temp = array[i];
            array[i] = array[minIdx];
            array[minIdx] = temp;
        }
    }
}

 

 

2. 삽입 정렬 (Insert Sort)

이미 정렬된 부분에 새로운 값을 삽입하는 정렬

using UnityEngine;

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

    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Insertion(array);
        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Insertion(int[] arr)
    {
        int n = arr.Length;

        for (int i = 0; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }
}

 

 

3. 버블 정렬 (Bubble Sort)

배열의 처음부터 끝까지 큰 값을 뒤로 밀어내는 정렬

using UnityEngine;

public class BubbleSort : MonoBehaviour
{
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };
    
    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Bubble(array);
        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Bubble(int[] arr)
    {
        int n = arr.Length;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

 

 

4. 퀵 정렬 (Quick Sort)

기준점을 잡아서 정렬하고 다시 기준점을 잡는 정렬

using Unity.VisualScripting;
using UnityEngine;

public class QuickSort : MonoBehaviour
{
    private int[] array = { 5, 2, 1, 8, 3, 7, 6, 4 };
    
    void Start()
    {
        Debug.Log("정렬 전 : " + string.Join(", ", array));

        Quick(array, 0, array.Length - 1);
        Debug.Log("정렬 후 : " + string.Join(", ", array));
    }

    private void Quick(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = Partition(arr, left, right);
            
            Quick(arr, left, pivot - 1);
            Quick(arr, pivot + 1, right);
        }
    }

    private int Partition(int[] arr, int left, int right) // 피봇을 활용해서 분할
    {
        int pivot = arr[right];
        int index = left - 1;

        for (int i = left; i < right; i++)
        {
            if (arr[i] < pivot)
            {
                index++;

                int temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
            }
        }

        int temp2 = arr[index + 1];
        arr[index + 1] = arr[right];
        arr[right] = temp2;

        return index + 1;
    }
}