[자료구조] 6. 그래프(Graph)

---

그래프(Graph)

그래프(Graph)

---

그래프(Graph)

특징, 장단점

특징
   1. 노드와 간선
   2. 방향성
   3. 간선마다 가중치
   4. 일부 그래프는 사이클이 포함될 수 있음

장점
   1. 다양한 데이터의 복잡한 관계 표현이 가능함
   2. 실세계 복잡한 시스템을 모델링할 수 있음
   3. 다양한 알고리즘 적용 가능

단점
   1. 대규모 그래프의 복잡성
   2. 상당한 양의 메모리를 요구함
   3. 알고리즘 최적화가 쉽지 않음

그래프 활용

탐색 그래프
게임 세계의 특정 위치나 지역을 노드가 나타내고, 간선은 위치 간의 이동 가능한 경로를 나타냄

네비게이션 그래프
AI가 이동할 수 있는 이동 경로를 나타낼 수도 있음

상호작용 그래프
게임 내 캐릭터나 객체가 노드이면, 간선은 이들 간의 관계나 상호작용을 표현함

그래프 알고리즘 활용 상황

경로 탐색 알고리즘 A*, 다익스트라 알고리즘, BFS, DFS
한 지점에서 다른 지점까지 최적, 유효한 경로를 찾음

게임 개발 활용

활용 예시    1. 경로 찾기
   2. 캐릭터 행동 제어 - 상태를 관리, 피해 시 방어 상태로 전환, 특정 조건
   3. NPC와 관계 모델링 - 친분, 플레이어의 결정에 따라 관계 변화 구현
   4. 오픈 월드 지도 설계 - 탐색 그래프를 통해 오픈 월드 지도에서의 탐험 여부 등록

---

TOP

---