정보·컴퓨팅 · 알고리즘 탐구 / 원리와 탐구
최단 경로 찾기 실험 해설
격자의 방문 순서와 최종 경로를 보고 두 탐색 방식을 비교해요.
어떤 원리인가요?
너비 우선 탐색은 칸 수를, 다익스트라는 비용 합을 최소로 해요.
핵심 관계
d(v) = min[d(u) + w(u,v)]
이렇게 관찰해 보세요
- 격자의 방문 순서와 최종 경로를 보고 두 탐색 방식을 비교해요.
- 기준 조건 세 가지를 각각 실행하고 측정값을 기록해요.
- 한 변수만 바꾸어 기준 기록과 결과를 비교해요.
결과를 읽는 기준
모든 칸 비용이 같으면 두 방식의 최단 거리는?
같아요 · 너비 우선 탐색은 칸 수를, 다익스트라는 비용 합을 최소로 해요.
모형의 범위와 한계
상하좌우 이동만 허용하고 비용은 양수예요. 벽 배치와 출발·도착은 재현 가능한 프리셋으로 바꿔요.