거리는 더 짧은데, 왜 더 늦게 도착할까요?
짧은 길에는 신호가 있습니다. 기다리는 시간을 바꿔 보면 답이 뒤집히는 지점이 있습니다.
가까운 길S → A → T선택됨
- 거리
- 400m
- 이동
- 4분
- 대기
- 4분
- 총시간
- 8분
돌아가는 길S → B → T
- 거리
- 600m
- 이동
- 6분
- 대기
- 0분
- 총시간
- 6분
이 모형에서 거리가 짧은 길은 가까운 길(S → A → T) 입니다. 400m 입니다.
가까운 길은 400m, 돌아가는 길은 600m 입니다. 대기시간은 거리에 영향을 주지 않습니다.
- 가까운 길(S → A → T): 거리 400m, 이동 4분, 대기 4분, 총 8분
- 돌아가는 길(S → B → T): 거리 600m, 이동 6분, 대기 0분, 총 6분
어떻게 계산했습니까
- 입력을 받습니다. 비교 기준(거리 또는 시간)과 기다리는 시간입니다.
- 갈 수 있는 길을 모두 찾습니다. 같은 지점을 두 번 지나는 길은 세지 않습니다. 이 지도에서는 2개입니다.
- 길마다 수치를 더합니다. 거리는 연결선 거리의 합, 시간은 이동시간의 합에 지나는 대기 지점 수만큼의 대기시간을 더합니다.
- 조건을 비교합니다. 고른 기준에서 값이 가장 작은 길을 찾고, 값이 같으면 모두 고릅니다.
- 결과를 보여 줍니다. 카드와 문장으로 같은 내용을 함께 적습니다.
지도가 바뀌어도 하는 일은 같습니다. 길을 모두 세고, 더하고, 견주어 고릅니다. 프로그램이 길을 안내하는 방식도 출발은 이와 같습니다.
알아 둘 점
- 지도와 수치는 학습용 가상 값입니다. 실제 이동시간이나 신호 주기, 통학로 안전을 안내하지 않습니다.
- 시간대에 따라 변하는 교통, 속도 차이, 일방통행, 길 막힘은 다루지 않습니다.
- 지점이 몇 개뿐인 지도에서 모든 길을 끝까지 세어 보는 단순한 모형입니다. 실제 내비게이션 알고리즘이 아닙니다.
- 입력값은 이 브라우저 안에서만 계산하며, 어디에도 보내거나 저장하지 않습니다.
참고 자료: Princeton Algorithms — Shortest Paths · Google Maps 가 경로를 정하는 방법
이어서 해볼 만한 실험
직접 해보기
병은 어떻게 퍼질까
점 하나에서 시작한 전염이 번지는 과정을 직접 조절해 봅니다.
준비 중
정렬 알고리즘 달리기
같은 막대를 서로 다른 방법으로 정렬하면 누가 먼저 끝날까.