[멋쟁이사자처럼 유니티 TIL] 2024_12_10(화) 강의 요약 및 정리(2)

 

자료구조: 그래프 (Graph)

그래프는 노드(정점)들과 그들을 연결하는 간선들의 집합으로 이루어진 자료구조

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

 

그래프의 주요 특징:

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

그래프의 구현 방법:

• 인접 행렬 (Adjacency Matrix): 2차원 배열을 사용하여 노드 간의 연결 관계를 표현합니다.
• 인접 리스트 (Adjacency List): 각 노드마다 연결된 노드들의 리스트를 유지합니다.

(295) EBS 링크 소프트웨어 세상, "가장 빠른길을 찾아라, 최단경로 알고리즘" - YouTube

 

AVL 트리

자동으로 균형을 맞추는 이진 탐색 트리로, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1.

 

 

public int height;

// 이 노드의 높이를 나타내는 변수

  트리의 균형을 맞추기 위해 AVL 트리에서는 각 노드의 높이를 계산해 놓음.

 

public Vector2 position;

// 이 노드의 화면상 위치를 나타내는 변수

  Vector2는 두 개의 값(x, y)을 갖는 구조체로, 주로 2D 공간에서 위치를 지정할 때 사용됨.

 

this.height = 1;

// 노드가 생성될 때 height 값을 1로 초기화

 

private Node root;

// root는 트리의 최상위 노드를 참조. 이 변수는 트리의 시작점이자 첫 번째 노드로 사용

  트리를 구현할 때, 루트 노드를 통해 모든 다른 노드들에 접근하거나 트리 구조를 변경할 수 있음.

 

Insert(i);

// Insert(i) 메서드를 호출(9번 반복후에 종료)

 

UpdatePositions(root, 0, 0, 2);

- 0, 0

  // 트리의 초기 위치(예: 화면 좌표)를 나타내는 값

- 2

  // 트리 노드들 간의 간격 또는 스케일 값을 나타냄

 

public void Insert(int data)

// 주어진 data 값을 이진 탐색 트리(BST)에 삽입하는 함수.

  이 함수는 InsertRec 함수로 재귀적인 삽입 작업을 위임함.

root = InsertRec(root, data)

// InsertRec()는 트리 구조에서 데이터를 삽입하는 재귀 함수.

  이 함수는 트리의 노드들을 하나씩 탐색하며 적절한 위치에 새로운 값을 삽입함.

  

if (node == null)

return new Node(data);

// 현재 노드가 null이면 새 노드를 삽입할 위치를 찾은 것

 

if (data < node.data)

node.left = InsertRec(node.left, data)

// 삽입하려는 값이 현재 노드의 값(node.data)보다 작으면

   왼쪽 서브트리로 재귀 호출 하여, 왼쪽 서브트리로 할당.

 

else if (data > node.data)

node.right = InsertRec(node.right, data);

// 삽입하려는 값이 현재 노드의 값(node.data)보다 크다면

  오른쪽 서브트리로 재귀 호출 하여, 오른쪽 서브트리로 할당.

 

else return node;

// 삽입하려는 값이 현재 노드의 값과 같으면 아무 것도 하지 않고 노드를 반환

 

UpdateHeight(node);

// 삽입 후 노드의 높이를 업데이트

 

return Balance(node, data);

// 트리의 균형을 맞추는 작업을 수행 (AVL 트리의 균형을 맞추는 함수)

 

return node == null ? 0 : node.height;

// 현재 노드가 null 이면, 0.  null 이 아니면 node.height 를 반환.

 

return node == null ? 0 : Height(node.left) - Height(node.right);

// 현재 노드가 null 이면, 0.  

   null 이 아니면 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 빼는 방식으로 계산.

 

if (node != null)

node.height = Mathf.Max(Height(node.left), Height(node.right)) + 1;

// node가 null 이 아니라면 하기의 코드를 실행

  왼쪽 자식 노드와 오른쪽 자식 노드의 높이 중 더 큰 값을 찾음

  (Mathf.Max(Height(node.left), Height(node.right)))

   나온 값에 +1 을 실행하여, 현재 노드의 높이를 설정.

 

Node x = y.left;

Node T2 = x.right;

// y의 왼쪽 자식 노드를 x로 설정

// x의 오른쪽 자식 노드를 T2로 설정

 

x.right = y;

y.left = T2;

// x의 오른쪽 자식을 y로 설정

// y의 왼쪽 자식을 T2로 설정

 

UpdateHeight(y);

UpdateHeight(x);

// y의 높이 업데이트

// x의 높이 업데이트

 

return x;

// 새로운 루트인 x를 반환

 

Node y = x.right;

Node T2 = y.left;

// x의 오른쪽 자식 노드를 y로 설정

// y의 왼쪽 자식 노드를 T2로 설정

 

y.left = x;

x.right = T2;

// y의 왼쪽 자식을 x로 설정

// x의 오른쪽 자식을 T2로 설정

 

UpdateHeight(x);

UpdateHeight(y);

// x의 높이 업데이트

// y의 높이 업데이트

 

return y;

// 새로운 루트인 y를 반환

 

int balance = GetBalance(node);

// 노드의 균형 계수를 계산

 

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

return RightRotate(node);

// 왼쪽 자식이 불균형하고, 새로운 데이터가 현재 노드의 왼쪽 자식 노드보다 작을 때

// 오른쪽 회전 (Right Rotation)

 

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

return LeftRotate(node);

// 오른쪽 자식이 불균형하고, 새로운 데이터가 현재 노드의 오른쪽 자식 노드보다 작을 때

// 왼쪽 회전 (Left Rotation)

 

if (balance > 1 && data > node.left.data)

node.left = LeftRotate(node.left);

return RightRotate(node);

// 왼쪽 자식이 불균형하고, 새로운 데이터가 현재 노드의 왼쪽 자식 노드보다 작을 때

// 왼쪽 자식에 대해 왼쪽 회전

// 오른쪽 회전 (Right Rotation)

 

if (balance < -1 && data < node.right.data)

node.right = RightRotate(node.right);

return LeftRotate(node);

// 오른쪽 자식이 불균형하고, 새로운 데이터가 현재 노드의 오른쪽 자식 노드보다 작을 때

// 오른쪽 자식에 대해 오른쪽 회전

// 왼쪽 회전 (LeftRotate)

 

return node;

// 트리가 균형을 이룬 경우 노드를 그대로 반환

 

UpdatePositions(Node node, float x, float y, float horizontalSpacing)

// AVL 트리의 노드들에 대한 2D 좌표를 계산하여 각 노드의 position을 설정

  트리의 구조를 화면에 그리기 위한 좌표 배치후

   각 노드가 트리 구조에 맞게 적절한 위치에 배치되도록 x, y 좌표를 갱신

 

if (node == null) return

// node가 null이면 더 이상 진행할 필요가 없으므로 종료

 

node.position = new Vector2(x, y)

// 현재 노드의 position을 Vector2(x, y)로 설정하여 이 노드의 2D 좌표를 정의

 

UpdatePositions(node.left, x - horizontalSpacing, y - 1.5f, horizontalSpacing / 2)

// 현재 노드의 왼쪽 자식에 대해, 수평 좌표 x를 왼쪽으로 이동

  수직 좌표 y를 아래로 내려가게 설정한 뒤

  수평 간격을 절반으로 줄여서 왼쪽 자식의 위치를 설정

 

UpdatePositions(node.right, x + horizontalSpacing, y - 1.5f, horizontalSpacing / 2)

// 현재 노드의 오른쪽 자식에 대해, 수평 좌표 x를 오른쪽으로 이동

  수직 좌표 y를 아래로 내려가게 설정한 뒤

  수평 간격을 절반으로 줄여서 왼쪽 자식의 위치를 설정

 

OnDrawGizmos()

// Unity에서 Gizmos를 사용하여 게임 오브젝트를 시각화할 때 사용

  이 함수 내부에서는 DrawNode(root)가 호출되며, 이를 통해 트리 구조를 그리게 됨.

 

if (root != null)

// 트리가 비어 있지 않으면, 트리의 루트 노드를 기준으로 그리기 시작.

 

DrawNode(root)

// 루트 노드를 그리기 위한 함수. 이 함수는 트리의 루트를 시작으로 각 노드를 시각적으로 표현할 수 있음.

 

 

Gizmos.color = Color.white

// 선의 색을 흰색으로 설정하고, Gizmos.DrawLine은 두 점을 연결하는 선을 그림

 

Gizmos.DrawLine(new Vector3(node.position.x, node.position.y, 0),

                               new Vector3(node.left.position.x, node.left.position.y, 0));

// 부모 노드(node.position)와 왼쪽 자식 노드(node.left.position) 간에 선을 그림

 

 Gizmos.DrawLine(new Vector3(node.position.x, node.position.y, 0),

                                new Vector3(node.right.position.x, node.right.position.y, 0));

// 부모 노드(node.position)와 오른쪽 자식 노드(node.right.position) 간에 선을 그림

 

Gizmos.color = Color.cyan;

// 원의색(Sphere)을 cyan 으로 설정함

 

Gizmos.DrawSphere(new Vector3(node.position.x, node.position.y, 0), 0.2f);

// (node.position.x, node.position.y, 0) 위치에 반지름 0.2f 크기의 구체를 그림

 

UnityEditor.Handles.Label(new Vector3(node.position.x, node.position.y + 0.3f, 0),

$" {node.data} (h:{node.height})");

- UnityEditor.Handles.Label

  // 노드의 데이터를 텍스트로 표시하는데 사용

- (node.position.x, node.position.y + 0.3f, 0)

  // 노드의 위치는 상기의 코드 로, 원의 위쪽에 약간 오프셋을 주어 텍스트를 표시함.

- $" {node.data} (h:{node.height})");

  // node.data는 노드의 데이터, node.height는 노드의 높이를 나타내며, 이 값들을 텍스트로 표시

 

DrawNode(node.left);

DrawNode(node.right);

// DrawNode(node.left)와 DrawNode(node.right)는 왼쪽 자식과 오른쪽 자식을 재귀적으로 그림

  이로 인해 트리 구조의 모든 노드가 그려짐.