길찾기 알고리즘, 언제 어떤 걸 써야 할까? 🧭

안녕하세요 logro 입니다 :)
오늘은 게임, 네비게이션, 로봇 경로 탐색 등에서 빠질 수 없는 길찾기 알고리즘(Pathfinding Algorithm) 들이 언제 사용되는지 간단하게 알아보는 시간을 가져볼게요!

길찾기 알고리즘은 크게 두 가지 경우에 따라 선택하게 돼요:

• 어떤 기준으로 최적 경로를 찾고 싶은가?
• 지도(그래프)의 구조가 어떤가?

그럼 대표적인 알고리즘들을 언제 쓰는지 간단하게 살펴볼까요? 😊

---

🐢 1. BFS (너비 우선 탐색)

• 언제 사용해요?
  모든 간선의 비용이 같을 때, 가장 빠른(짧은) 경로를 찾고 싶을 때!
• 예시
  미로 탈출, 단순한 격자 지도 등

---

🐇 2. 다익스트라(Dijkstra)

• 언제 사용해요?
  이동 비용(가중치)이 다를 때, 가장 저렴한 비용의 경로를 찾고 싶을 때!
• 예시
  네비게이션 앱에서 최단 거리 찾기, 물류 배송 경로 등

---

🌟 3. A* (에이 스타)

• 언제 사용해요?
  목표 지점까지의 예상 거리(휴리스틱) 를 활용해서 더 빠르게 경로를 찾고 싶을 때!
• 예시
  게임 캐릭터 AI, 로봇 경로 탐색 등
  (실시간으로 빠르게 길 찾아야 할 때 좋아요!)

---

📦 4. 플로이드 워셜(Floyd-Warshall)

• 언제 사용해요?
  모든 정점 쌍 사이의 최단 거리를 한 번에 구해야 할 때!
• 예시
  전체 도시 간 거리 계산, 그래프 전체 분석 등

---

🛣️ 5. 벨만 포드(Bellman-Ford)

• 언제 사용해요?
  간선에 음수 가중치가 있을 때! (다익스트라는 음수 가중치에서 오작동해요)
• 예시
  통화 환율 계산, 비용이 음수일 수 있는 상황 등

---

🚧 한눈에 정리!

알고리즘	비용 다양성	음수 허용	휴리스틱 사용	언제 사용?
BFS	X	X	X	모든 간선 비용이 같을 때
다익스트라	O	X	X	비용이 다를 때
A*	O	X	O	빠르게 목표에 도달해야 할 때
플로이드 워셜	O	O	X	전체 경로 정보가 다 필요할 때
벨만 포드	O	O	X	음수 가중치가 있을 때

휴리스틱, 문제 해결의 직감적 길잡이 🧭

휴리스틱, 문제 해결의 직감적 길잡이 🧭

 

---

길찾기 알고리즘은 상황에 따라 적절한 걸 고르는 게 정말 중요해요!

앞으로 하나씩 자세히 알아보면서, 여러분의 ‘알고리즘 나침반’을 더 정확하게 만들어볼게요 🔍