[Unity 게임 개발을 위한 C# 공부 일지] 길찾기 - 2 (그래프)

본 포스팅은

'[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈]' 인프런 강의를 수강 후, 개인적으로 배운 내용을 정리합니다.

코드의 경우에는 강사님의 저작권을 훼손할 염려가 있어 결과의 모습, 이론적인 내용을 중점으로 정리합니다.

---

스택과 큐

둘 다 선형자료구조.

자료들이 일자로 나열되어 있는 형태

 

스택: LIFO(후입선출,  Last In First Out)

사용 예시 ) User가 UI창을 여러개 띄우는 경우, UI 창이 꺼질때 나중에 켜진 창이 먼저 꺼지는 식으로 꺼진다.

 

 

큐 : FIFO(선입선출, First In First Out)

사용 예시)멀티플레이 게임이라면, 서버로 한순간에 여러 요청이 들어올텐데 그 때 먼저 들어온 요청부터 처리한다.

---

그래프

현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현

그래프의 구성요소 2가지

정점(Vertex), 간선(Edge)

정점 - 데이터를 표현한다 (사물, 개념)

간선 - 정점들을 연결하는데 사용

 

가중치 그래프 

ex) 지하철 노선도

최적 길찾기? 어떤 Vertex에서 어떤 Vertex로 이동시 최적의 경로찾기

(edge별로 가중치, 즉 소요시간이 다르기 때문에)

 

방향 그래프

간선에 방향이 있는것.

이전에는 방향이 없어 무조건 양방향 이동이 가능했으나

A, B vertex가 있다고 하면

A는 B로는 갈 수 있으나  B는 못 가는 그런 것. 간단히 생각하면 두 사람의 호감도나, 도로망 

 

그래프의 표현

위에서 말한 그래프들을 코드상 어떻게 표현하는것이 좋은가?

1. LinkedList 의 Node와 유사하게 인스턴스를 생성하면 어떤가?

Vertex 인스턴스를 생성해서 연결(edge)

안되는건 아니지만, 아쉬운 부분?

매번 인스턴스를 생성하여 vertex를 연결해야 한다.

이에 대한 대안으로 List를 사용하는 방법

 

2. List 활용

각 Vertex마다 연결된 Vertex를 List 내에 넣는것.

근본적으로는 아까와 큰 차이는 없다.

 

Vertex를 New하던 것을 줄였다. 메모리를 아낄 수 있으나 접근속도에서 손해를 보는 편

Vertex가 많고 Edge가 적은 경우 이득

 

3. 행렬 이용하기 (2차원 배열)

Vertex가 6개라고 하면 6 by 6 2차원 배열 생성

메모리의 소모는 심하지만, 빠른 접근이 가능하다.

Vertex가 적고 Edge가 많은 경우 이득인 편.

 

그래프를 탐색하는 두 가지 방법 - DFS, BFS

 

DFS (Deep First Search)

깊이 우선 탐색방법이다.

탐색 순서는 아래 그림과 같다.

 

BFS(Breadth First Search)

너비 우선 탐색방법이다.

탐색 순서는 아래 그림과 같다.

 

그림을 통해 DFS와 BFS의 차이점을 알 수 있겠는가?

DFS는 깊이 우선이므로 자신과 연결된 정점으로 이동... 그리고 또 그 정점과 연결된 정점으로 계속해서 탐색하는 방식,

BFS는 너비 우선이므로 자신과 연결된 모든 정점을 탐색한 후, 자신과 연결된 정점중 하나와 연결된 정점을 탐색해나가는 방식이다. 

 

---

BFS를 활용한 길 찾기.

저번에는 우수법을 사용하여 미로에서 길 찾기를 하였다.

하지만, 미로를 만들어낸 2차원 배열또한 어떻게 보면 행렬로써 일반 Graph와 같기 때문에 BFS를 사용하여 길찾기를 할 수 있다. 

방식은 이와 같다.

출발점으로부터 도착지점까지 BFS를 사용하여 탐색을 하다, 도착지점에 닿으면 탐색을 멈추고.

도착지점에 도달했던 것의 경로만 출발점으로 거슬러 올라가며 저장한 후, 그 길을 다시 역으로 재생하면

출발지로부터 도착지점까지의 길이다.

 

이게 무슨 소리인지 설명이 부족하여 잘 이해가 안 갈 수 있기에 좀 더 자세한 설명을 덧붙여 보자면...

미로에서 이런 길이 있다고 치면, 이 길의 정중앙을 지나는 다음 순간부터.

거의 동시에 4갈래의 길을 탐색하게 되는 것이다.

즉, 탐색하는 길이 우수법처럼 한가지가 아니라 여러가지가 된다는 뜻인데, 그럼 이 탐색하는 길이 많을 때 어떤 길이 가장 짧은길인가를 알 수 있는 방법은 간단하다.

그냥 가장 먼저 도착하면 그 길이 짧은 길인것이다!

그렇기 때문에 다른 길을 무시하기 위해서 가장 먼저 도착했다면 그 점이 온 길만 역순으로 따 준후 역재생하면

통상의 최단루트를 찾을 수 있게 된다는 것이다.

이를 사용한 실제 길찾기 영상이다.

 

---

다익스트라 알고리즘

단, 위와같은 BFS는 가중치가 없는 일반그래프에서만 사용이 가능하다는 부분이 있다.

왜냐하면 엣지에 가중치가 붙게 되는순간부터 단순히 경로사이의 엣지개수를 최소화하는것만이 최소루트가 아니게 되기 때문이다.

대충 그린 그래프이다. 한 번 보자.

A에서 C로 가는 경로는 2가지가 된다.

1) A -> B -> C

2) A -> C

이 경우, 어떠한 경로가 가장 비용이 적게 드는 경로인가? 라고 묻는다면

1) A->B->C 가 된다, 왜? A->C보다 경유하는 곳이 하나가 더 많지만 총 비용이 적기 때문.

 

그렇다고 해서 단순히 무턱대고 비용이 짧은길만 택해서 움직여서도 안된다.

가랑비에 옷 젖는지 모른다고, 짧은줄 알았는데 쌓이고 쌓여서 비용이 눈더미처럼 불어난다.

그렇기 때문에 BFS를 응용하면 된다.

한 지점에서 한 지점까지 가는데 드는 최소비용을 계속해서 계산해서 업데이트해 나가면서 하는 것이다.

뭔가 이해는 하는데 막상 설명하려고 하니 좀 막막한 감이 없잖아 있다.

개인적으로는 전에 알고리즘 문제를 풀 당시, DP(동적 계획법)와 동일, 혹은 유사하다고 생각한다.

그래서 이해하기가 좀 쉬웠는데 설명하기는 어렵다...

솔직한 심정으로는 관련 문서를 몇 번 읽어보고  DP문제를 조금 풀어보는게 많은 도움이 될 거라고 생각한다.

 

 

여기까지가 그래프에 관한 공부 내용이다.

다음에는 트리에 관해 배워 본 후 A* 트리를 활용한 길찾기 까지 해 볼 예정이다.