트리와 그래프
트리
Tree
- 계층적 구조를 표현하는 '비선형' 자료구조
- 노드들과, 노드들을 연결하는 간선들로 구성
- 하나의 루트 노드, 각 노드는 0개 이상의 자식 노드를 가질 수 있음, 사이클 존재 X
종류
- 일반 트리(General Tree) : 노드가 임의의 수의 자식을 가질 수 있는 트리
- 이진 트리(Binary Tree) : 각 노드가 최대 2개의 자식을 가질 수 있는 트리
- 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
- 포화 이진 트리(Perfect Binary Tree) : 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 갖는 이진 트리
- AVL 트리 : 자동으로 균형을 맞춰주는 이진 탐색 트리의 일종, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1
- 레드 블랙 트리(Red - Black Tree) : 자가 균형 이진 탐색 트리의 일종, 색상 속성을 사용하여 균형을 유지
- B - 트리 : 데이터베이스와 파일 시스템에서 사용되는 균형 검색 트리, 노드에 여러개의 키를 저장할 수 있음
구조와 용어
- 노드 : 트리를 구성하는 기본 요소, 데이터 저장
- 간선 : 노드와 노드를 연결하는 선
- 루트 노드 : 트리의 최상위에 있는 노드
- 부모 노드 : 직접적인 상위 노드
- 자식 노드 : 직접적인 하위 노드
- 리프 노드 : 자식이 없는 노드, 트리의 끝단에 위치
- 깊이 : 루트에서 특정 노드까지의 경로 길이
- 높이 : 노드에서 가장 먼 리프까지의 경로 길이
트리의 순회 방법
순회 : 트리의 모든 노드를 체계적으로 방문하는 과정
- 전위 순회(Preorder) : 루트 > 왼쪽 서브트리 > 오른쪽 서브트리
- 중위 순회(Inorder) : 왼쪽 서브트리 > 루트 > 오른쪽 서브트리
- 후위 순회(Postorder): 왼쪽 서브트리 > 오른쪽 서브트리 > 루트
- 레벨 순회(Level -order): 루트부터 레벨별로 왼쪽에서 오른쪽으로 순회
참고되는 좋은 유튜브 !
https://www.youtube.com/watch?v=QN1rZYX6QaA
재귀 관련 내용
https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60
재귀함수의 장점과 단점 그리고 해결책
재귀(Recursion)란?
catsbi.oopy.io
이제 직접 순회를 구현해보자.
public class BinaryTree : MonoBehaviour
{
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int item)
{
data = item;
left = right = null;
}
}
노드를 정의해주고 생성자를 생성해준다.
이 노드는 데이터와, left, right 노드를 가르키는 값을 지닌다.
생성자로 초기화해준다.
Preorder
pre(미리) 루트를 말하고 왼쪽, 오른쪽순서대로 순회한다.
- 루트 노드를 호출한다.
- 왼쪽(left) 서브트리로 향한다.
- 또 Preorder 기능을 사용한다. (반복) - 오른쪽(right) 서브트리로 향한다.
- Preorder 기능을 사용한다. (반복)
반복이 노드의 끝에 가면 멈춰야 하므로 , 노드가 null이라면 돌아가 다른 과정을 수행해야 한다.
public void Preorder(Node node)
{
if (node == null)
return;
Debug.Log(node.data + " "); // 루트
Preorder(node.left); // 왼쪽 서브트리
Preorder(node.right); // 오른쪽 서브트리
}
Inorder
In(~안에), 루트 노드를 중간에 말하며 순회한다..
public void Inorder(Node node)
{
if (node == null)
return;
Inorder(node.left); // 왼쪽 서브트리
Debug.Log(node.data + " "); // 루트
Inorder(node.right); // 오른쪽 서브트리
}
Postorder
post(후에), 루트 노드를 마지막에 말하며 순회한다.
public void Postorder(Node node)
{
if (node == null)
return;
Postorder(node.left); // 왼쪽 서브트리
Postorder(node.right); // 오른쪽 서브트리
Debug.Log(node.data + " "); // 루트
}
순회에서 추가로 알아볼 것 : 레벨 순회
활용
- 전위 순회 : 게임 오브젝트의 복사나 직렬화에 유용함
- 중위 순회 : 이진 검색 트리에서 정렬된 순서로 노드를 방문할 때 사용
- 후위 순회 : 게임 오브젝트의 삭제나 메모리 해제 시 유용함
- 레벨 순회 : UI 요소의 계층적 렌더링이나 게임 로직의 단계별 처리에 적합
그래프
Graph
- 노드(정점)들과, 노드들을 연결하는 간선들의 집합으로 이루어진 자료구조
- 트리와 달리 순환이 허용되며, 더 유연한 관계 표현이 가능함
특징
- 방향성 : 방향 그래프와 무방향 그래프로 구분
- 가중치 : 간선에 비용이나 거리 등의 가중치를 부여 가능
- 순환성 : 순환이 허용되어 한 노드에서 시작해같은 노드로 돌아올 수 있음
- 연결성 : 모든 노드가 연결되어 있지 않을 수 있음
구현 방법
- 인접 행렬 : 2차원 배열을 사용하여 노드 간의 연결 관계 표싲
- 인접 리스트 : 각 노드마다 연결된 노드들의 리스트 유지
주요 알고리즘
- 깊이 우선 탐색(DFS) : 한 방향으로 깊이 탐색하다가 더 이상 갈 수 없으면 백트래킹
- 너비 우선 탐색(BFS) : 현재 노드와 가까운 노트부터 탐색
- 다익스트라 알고리즘 : 가중 그래프에서 최단 경로를 찾음
- 크루스칼 알고리즘 : 최소 신장 트리를 찾음
Unity에서 그래프의 활용
- 게임 맵 구현 : 이동 가능 지점들을 노드로, 경로들을 간선으로 표현
- AI 경로찾기 : A* 알고리즘 등을 사용한 내비게이션 시스템 구현에 활용
- 소셜 네트워크 : 플레이어 간의 관계나 상호작용을 표현
- 퀘스트 시스템 : 퀘스트 간의 의존성이나 진행 경로를 표현
알고리즘 구현
우선 Vertex(정점)을 구현해준다.
Vertex에는 이름 데이터와 이웃들에 대한 정보가 Dictionary형으로 저장되어 있다
Dictionary형을 쓴 이유는, 다른 정점까지의 거리를 저장하기 위함이다.
Ex) 집(name)에서 마켓까지의 거리(7km)를 (마켓, 7)로 neighbors라는 사전에 저장
생성자를 이용해 초기화를 해 준다.
using UnityEngine;
using System.Collections.Generic;
public class Graph : MonoBehaviour
{
public class Vertex
{
public string name;
public Dictionary<Vertex, float> neighbors;
public Vertex(string name)
{
this.name = name;
neighbors = new Dictionary<Vertex, float>();
}
}
}우리가 방금 만든 것은 한 Vertex를 만든 것이므로, Vertex들을 담을 변수도 하나 만들어 준다.
private Dictionary<string, Vertex> vertices;
void Start()
{
vertices = new Dictionary<string, Vertex>();
}
Vertex를 추가하기 위한 코드를 만든다.
public void AddVertex(string name)
{
if (!vertices.ContainsKey(name))
{
vertices.Add(name, new Vertex(name));
Debug.Log($"정점 {name}이(가) 추가되었습니다.");
}
}* 이미 있는 이름이라면 추가되면 안되니까, !vertices.ContainsKey(name), 즉 이름이 없다면 ~ 이다.
Vertex들 간의 간선도 추가해준다.
// 간선 추가 (가중치 있는 방향 그래프)
public void AddEdge(string fromName, string toName, float weight)
{
if (vertices.ContainsKey(fromName) && vertices.ContainsKey(toName))
{
Vertex from = vertices[fromName];
Vertex to = vertices[toName];
if (!from.neighbors.ContainsKey(to))
{
from.neighbors.Add(to, weight);
Debug.Log($"간선 {fromName} -> {toName} (가중치: {weight})가 추가되었습니다.");
}
}
}
가중치가 있는 방향이므로, 매개변수는 시작점, 도착점, 가중치이다.
만들어진 정점에 시작점과 도착점이 존재한다면
from에 시작점을 할당, to에 도착점을 할당한다.
이미 간선이 있으면 안되므로, 만일 from이라는 vertex의 이웃(사전 자료형)에 이미 to(도착점의 Vertexname)이 없다면
간선과 가중치를 추가해준다.
너비 우선 탐색 (Breadth first search)
위 그림과 같은 과정을 구현하려면 어떻게 해야할까 ? 순회와 마찬가지로 재귀함수를 사용해야 할 것이다.
조건은, 한 번 탐색된 노드가 다시 탐색되지 않는 것, 루트와 가까운 노드부터 순서대로 (깊이가 짧은) 탐색할 것,
모든 노드를 탐색할 것과 같은 조건이 있다.
조건을 만족하기 위해서, HashSet이라는 중복을 허용하지 않는 자료형과, queue를 사용했다.
Queue를 사용한 이유는, 먼저 탐색된 노드에서 또 탐색을 시작하기 위함이다.
우선, BFS 함수를 만들고, 예외처리 ( 정점들에 startName이 없을 경우)를 해 준다.
그리고 방문한 곳은 또 방문하지 않게 하기 위한 HashSet 자료형의 visited와 탐색 순서를 위한 queue 변수를 만든다.
public void BFS(string startName)
{
if (!vertices.ContainsKey(startName)) return;
HashSet<Vertex> visited = new HashSet<Vertex>();
Queue<Vertex> queue = new Queue<Vertex>();
}
시작점을 할당해주고, 시작할 때에 시작점을 방문했으니 visited 데이터에 넣어주고, queue 데이터에도 넣어준다.
Vertex start = vertices[startName];
queue.Enqueue(start);
visited.Add(start);
방문할 곳이 남아 있으면 계속해서 진행되어야 하므로 while문을 써서 루프를 만들어준다.
그리고 현재 위치는 Dequeue를 통해 반환받으며 확인을 위해 로그를 찍는다.
while (queue.Count > 0)
{
Vertex current = queue.Dequeue();
Debug.Log($"방문: {current.name}");
}while문 안에, 가까운 곳(neighbor) 을 모두 방문할 수 있도록 foreach문을 사용한다.
방문한 곳은 또 방문하면 안되므로, 방문하지 않았다는 조건(!visited.Contains(neighbor)을 달아준다.
방문하게 되면, visited 에 추가하고, queue에도 추가한다.
모든 neighbor들을 방문하고, while문으로 돌아가 가장 먼저 방문한 곳의 데이터를 current로 받으며(Dequeue) 진행을 계속한다.
foreach (var neighbor in current.neighbors.Keys)
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
코드 전문은 다음과 같다.
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)
이 경우에는 반복문을 두 개 쓸 필요가 없다 , 우리가 트리의 순회에서 했던 것과 비슷한 구조로 코드를 짜 준다.
앞의 경우(BFS)와 마찬가지로, 정점들 안에 startName이 없으면 return하는 예외처리를 하고,
방문한 곳을 기록하기 위한 HashSet 자료형을 visited로 만든다.
// 깊이 우선 탐색 (DFS)
public void DFS(string startName)
{
if (!vertices.ContainsKey(startName)) return;
HashSet<Vertex> visited = new HashSet<Vertex>();
DFSUtil(vertices[startName], visited);
}DFSUtil은 다음과 같은 함수이다.
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);
}
}
}방문한 곳을 visited에 추가하고, 로그를 찍는다.
방문한 곳의 이웃에 들어가 그 이웃이 방문되지 않은 곳이라면 다시 한 번 그 곳을 기준으로 DFSUtil을 실행한다
즉 위 BFS와 다른 점은, BFS에서는 모든 이웃들을 방문하고 다음에 처음 방문한 이웃들의 이웃을 방문했는데
DFS에서는 한 이웃을 방문하고, 또 거기서 바로 이웃의 이웃을 방문한다는 점이다.
다익스트라 최단 경로 알고리즘
일단, 수업 시간에 당장 이해되는건 이정도였다.
여기서 추가로, AVl, 레드블랙 트리, 다익스트라 최단 경로 알고리즘은...아직...이해가 안가서 밥 먹고 조금 더 공부하고 따로 올려봐야겠다.
'TIL' 카테고리의 다른 글
| [멋쟁이사자처럼 부트캠프 TIL회고] Unity 게임개발 3기 23일차 (1) | 2024.12.12 |
|---|---|
| [멋쟁이사자처럼 부트캠프 TIL회고] Unity 게임개발 3기 22일차 (0) | 2024.12.12 |
| [멋쟁이사자처럼 부트캠프 TIL회고] Unity 게임개발 3기 21일차 (3) | 2024.12.10 |
| [멋쟁이사자처럼 부트캠프 TIL회고] Untiy 게임개발 3기 20일차 (3) | 2024.12.09 |
| [멋쟁이사자처럼 부트캠프 TIL회고] Unity 게임개발 3기 19일차 (0) | 2024.12.07 |