🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)
최단 거리 = 맵에서 현재 방에서 목표 방까지 문을 최소로 지나가는 경로, 또는 이동 비용(걸음 수·시간)이 가장 적은 경로를 구할 때 씁니다. 간선 비용이 모두 같으면 BFS로, 비용이 다르면 다익스트라로 구해요. NPC 이동 경로, 미니맵 최단 경로 표시, 퀘스트 "가장 가까운 목표" 찾기 등에 활용됩니다.
최단 거리
그래프에서 한 점에서 다른 점까지 가장 짧은 경로를 구하는 거예요. 간선에 거리(가중치)가 있으면 그 합이 최소가 되는 경로를 찾습니다.
BFS(비에프에스)
간선의 가중치가 모두 같을 때(예: 1), BFS(너비 우선 탐색)로 최단 거리를 구할 수 있어요. 가까운 것부터 층층이 방문하면 됩니다.
다익스트라(Dijkstra, 다익스트라)
가중치가 다를 때는 다익스트라 알고리즘 등을 씁니다. 시험에 "단계별로 어떤 점이 선택되는지" 묻는 문제가 나올 수 있어요.
😄 조크 다른 과목에서는 복사·붙여넣기가 표절인데, 프로그래밍에서는 "코드 재사용"이라고 부른대요. 더 보기 →
이 강의는 개념만 다뤄요. BFS·다익스트라 코드 실습은 교과·실기 자료에서 다루는 경우가 많아요. 탐색 기초 실습은 1. 순차·이진 탐색에서 해요.