[자료구조] Graph와 길찾기

1. Graph가 무엇인지 알고 있나요?

• 정점 ( Node/Vertex)과 간선 (Edge)로 이루어진 자료구조

---

2. Tree는 Graph인가요? Graph는 Tree인가요?

• 트리는 그래프의 일종이지만, 그래프는 정점마다 간선이 존재하지 않을 수도 있고 루트 노드와 부모 노드, 자식 노드 개념이 존재하지 않기 때문에 트리가 아니다.

---

3. NavMesh가 길찾기를 위해 사용하는 알고리즘은 무엇인가요?

• A* 알고리즘을 이용하여 최단 경로를 계산한다.

---

4. 길찾기 알고리즘에 대해 알고 있는 것이 있나요?

• BFS 알고리즘
  • 너비 우선 탐색으로 현재 위치에서 가까운 노드부터 탐색하여 점차 멀리 있는 노드를 탐색한다.
• 다익스트라 알고리즘
  • 가중 그래프에서 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
  • 가중치가 음수인 경우에는 최단 경로를 구할 수 없다.
• 벨만 포드 알고리즘
  • 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
  • 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있지만 시간 복잡도가 O (V * E)로 다익스트라보다 느리다.
• 플로이드 워셜 알고리즘
  • 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘입니다.
  • 그래프 내 모든 정점 쌍에 대한 최단 경로를 구하지만, 시간 복잡도가 O(V^3)이기 때문에 노드 수가 많을 경우 비효율적이다.

---

5. 각 길찾기 알고리즘의 차이점은 무엇인가요?

• BFS: 무가중 그래프에서 최단 경로를 찾는 데 적합. 모든 노드를 같은 순서로 탐색.
• A* : 휴리스틱을 사용하여 시작 지점에서 목적지까지의 최단 경로를 효율적으로 찾음. 특정 목표 지점에 대해 최적화.
• 다익스트라: 가중 그래프에서 출발점에서 다른 모든 정점까지의 최단 경로를 찾음. 가중치가 모두 양수일 때 사용.
• 벨만-포드: 음수 가중치가 있는 그래프에서도 작동하며, 음수 사이클을 감지할 수 있음.
• 플로이드-워셜: 모든 정점 쌍 간의 최단 경로를 계산. 작은 그래프에 적합하며, 큰 그래프에는 비효율적.

---

6. A* 알고리즘에 대해 설명해주세요.

• 시작 지점에서 목적지까지의 최단 경로를 휴리스틱 함수(추정 비용)를 사용하여 효율적으로 찾는 알고리즘
• 휴리스틱 값
  • 출발지에서 목적지까지 도달하기 위해서 남은 거리를 대략적으로 나타내는
• 구성요소:
  • g(n): 시작 지점에서 현재 노드 n까지의 실제 비용.
  • h(n): 현재 노드 n에서 목표 지점까지의 추정 비용(휴리스틱 함수).
  • f(n) = g(n) + h(n): 현재 노드 n의 총 비용..
• 장점: 효율적이고, 최적 경로를 보장할 수 있다.
• 단점: 휴리스틱 함수가 부정확할 경우 성능이 저하될 수 있다.