[C#] 비선형 자료구조 - Tree 실습하기

[확인문제]

 

1. Tree가 무엇인지 알고 있나요? Tree의 종류에는 어떤 것들이 있나요?

Tree는 계층적인 구조를 가지는 데이터 구조로, 노드(Node)와 간선(Edge)으로 이루어져 있다. 루트 노드(Root Node)에서 시작하여 각 노드는 자식 노드(Child Node)를 가질 수 있다. 대표적인 트리의 종류로는 이진 트리(Binary Tree), AVL 트리, 이진 탐색 트리(Binary Search Tree), B 트리, 힙(Heap) 등이 있다.

 

2. 다음의 트리를 DFS로 방문할 때와 BFS로 방문할 때의 순서가 어떻게 될까요?

DFS (Depth-First Search) 순서: 1 -> 2 -> 6 -> 9 -> 3 -> 7 -> 4 -> 8 -> 5

BFS (Breadth-First Search) 순서: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

 

 

 

3. 아래와 같은 형식의 미니맵이 있습니다. 나의 현재 위치로부터 보스방까지 어떻게 가야 가장 빠르게 갈 수 있는지 체크하려고 합니다. DFS와 BFS 중 어느 방법이 더 적절할까요?

BFS가 더 적절하다. BFS는 최단 경로를 찾는 데 유리하며, 특히 모든 간선의 가중치가 동일할 때 가장 짧은 경로를 보장한다. DFS는 경로를 찾을 수 있지만, 최단 경로를 보장하지 않습니다.

 

 

 

[설명문제]

 

1. Tree의 순회(Traversal) 방법에 대해 설명해주세요.

순회의 예시는 첫번째 사진의 트리로 하였다.

 

전위 순회 (Pre-order Traversal): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

전위 순회는 루트노드를 먼저 방문한 다음, 왼쪽 서브트리와 오른쪽 서브트리를 순회한다.

1 -> 2 -> 3 -> 6 -> 9 -> 7 -> 4 -> 8 -> 5

 

중위 순회 (In-order Traversal): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리

왼쪽 서브트리를 먼저 순회한 다음, 루트 노드를 방문하고, 오른쪽 서브트리를 순회한다.

2 -> 9 -> 6 -> 3 -> 7 -> 1 -> 4 -> 8 -> 5

 

후위 순회 (Post-order Traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

왼쪽 서브트리를 먼저 순회한 다음, 오른쪽 서브트리를 순회하고, 마지막으로 루트 노드를 방문한다.

9 -> 6 -> 7 -> 3 -> 2 -> 8 -> 4 -> 5 -> 1

 

2. DFS와 BFS에 대해 설명해주세요.

    a. DFS와 BFS를 본인의 프로젝트에 활용한 경험이 있다면 설명해주세요.

BFS (Breadth-First Search):

DFS는 가능한 깊숙이 탐색하는 방법입니다. 스택(Stack)이나 재귀를 사용하여 구현할 수 있다.

사용 예시: 퍼즐 문제 해결, 모든 경로 탐색 등.

 

BFS (Breadth-First Search):

BFS는 가까운 노드부터 차례대로 탐색하는 방법입니다. 큐(Queue)를 사용하여 구현한다.

사용 예시: 최단 경로 찾기, 네트워크 탐색 등.

 

활용 경험:

프로젝트에서 미로 탐색 알고리즘을 구현할 때 DFS와 BFS를 사용했다. DFS는 모든 가능한 경로를 찾는 데 사용했고, BFS는 출발 지점에서 목표 지점까지의 최단 경로를 찾는 데 사용했다.

3. 행동 트리 (Behaviour Tree) 에 대해 설명해주세요.

행동 트리는 인공지능 분야에서 많이 사용되는 트리 구조로, 행동을 결정하는 데 사용된다. 각 노드는 특정 조건이나 행동을 나타내며, 트리의 루트에서 시작하여 조건을 검사하고 행동을 수행한다. 주로 게임 AI와 로봇 제어 시스템에서 사용된다.

 

 

 

[실습문제]

 

💡 [최소 힙을 사용해 카드 정렬하기]

 

카드 게임의 AI를 만들고 싶습니다.

가장 초급 AI를 먼저 만드려고 하는데, 이 초급 AI는 매 턴 가장 작은 비용의 카드를 사용하게 설정하려고 합니다.

이 경우 매 턴마다 가장 적은 비용의 카드를 손에서 탐색해야하는 걸까요?

고민하고 있던 도중 최소 힙(Min Heap)에 대해 알게 되어 이를 이용하여 가장 작은 비용의 카드가 항상 앞에 있게 하려고 합니다.

이미 구현된 최소 힙을 이용하여 카드의 기능을 완성해봅시다.

MinHeap 기능

• public void Insert(T item): 새로운 요소를 힙에 삽입하고 힙의 속성을 유지합니다.
• public T ExtractMin(): 최소 요소를 제거하고 반환합니다. 제거 후 힙의 속성을 유지합니다. 힙이 비어 있으면 예외를 던집니다.
• public T Peek(): 힙의 최소 요소를 반환합니다. 힙이 비어 있으면 예외를 던집니다.
• private void HeapifyUp(int index): 주어진 인덱스에서 위로 올라가며 힙의 속성을 유지합니다.
• private void HeapifyDown(int index): 주어진 인덱스에서 아래로 내려가며 힙의 속성을 유지합니다.

class Program
{
    static void Main(string[] args)
    {
        // 카드 풀 생성
        List<Card> cardPool = new List<Card>
            {
                new Card("Fireball", 5),
                new Card("Ice Bolt", 3),
                new Card("Healing Potion", 2),
                new Card("Shield", 4)
            };

        // 랜덤 객체 생성
        Random rand = new Random(1);

        // MinHeap 생성
        MinHeap<Card> cardHeap = new MinHeap<Card>();


        // 카드 풀에서 랜덤하게 5장의 카드를 뽑아 힙에 삽입
        for (int i = 0; i < 5; i++)
        {
            int randomIndex = rand.Next(cardPool.Count);
            cardHeap.Insert(cardPool[randomIndex]);
        }

        // TODO: cardHeap이 빌 때까지 가장 적은 비용의 카드만 내기
        
    }

    static void PlayCard(Card card)
    {
        Console.WriteLine($"Playing card: {card}");
    }
}

public class Card : IComparable<Card>
{
    public string Name { get; set; }
    public int Cost { get; set; }

    public Card(string name, int cost)
    {
        Name = name;
        Cost = cost;
    }

    public int CompareTo(Card other)
    {
        if (other == null) return 1;
        return Cost.CompareTo(other.Cost);
    }

    public override string ToString()
    {
        return $"{Name} (Cost: {Cost})";
    }
}

public class MinHeap<T> where T : IComparable<T>
{
    private List<T> heap;

    public MinHeap()
    {
        heap = new List<T>();
    }

    public int Count => heap.Count;

    public void Insert(T item)
    {
        heap.Add(item);
        HeapifyUp(heap.Count - 1);
    }

    public T ExtractMin()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        T min = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);

        if (heap.Count > 0)
            HeapifyDown(0);

        return min;
    }

    public T Peek()
    {
        if (heap.Count == 0)
            throw new InvalidOperationException("Heap is empty.");

        return heap[0];
    }

    public void DisplayHeap()
    {
        Console.WriteLine("Current cards in heap:");
        foreach (T item in heap)
        {
            Console.WriteLine(item);
        }
        Console.WriteLine();
    }

    private void HeapifyUp(int index)
    {
        int parentIndex = (index - 1) / 2;

        if (index > 0 && heap[index].CompareTo(heap[parentIndex]) < 0)
        {
            Swap(index, parentIndex);
            HeapifyUp(parentIndex);
        }
    }

    private void HeapifyDown(int index)
    {
        int smallest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heap.Count && heap[leftChild].CompareTo(heap[smallest]) < 0)
        {
            smallest = leftChild;
        }

        if (rightChild < heap.Count && heap[rightChild].CompareTo(heap[smallest]) < 0)
        {
            smallest = rightChild;
        }

        if (smallest != index)
        {
            Swap(index, smallest);
            HeapifyDown(smallest);
        }
    }

    private void Swap(int index1, int index2)
    {
        T temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }
}

 	// TODO: cardHeap이 빌 때까지 가장 적은 비용의 카드만 내기
        while(cardHeap.Count > 0)
        {
            PlayCard(cardHeap.ExtractMin());
        }