✍️ 문제 3-2
제9회 소프트웨어(SW) 사고력 올림피아드(중1~3)
※ 다음 문제에 답하시오.
※ 답은 종이에 작성한 뒤 사진으로 제출하세요.
※ 창의적인 생각을 자유롭게 기록해도 됩니다.
문제 3
아래 그림은 도시 사이의 길과 차비를 보여준다. 화살표는 갈 수 있는 방향을 나타내며, 화살표에 붙은 숫자는 차비를 의미한다. ㉮에서 ㉯로 가는 길 중 가장 차비가 적게 드는 길을 찾으려 한다.
문제 3-2
위 3-1과 같은 문제를 자동으로 해결하는 알고리즘 코드를 작성하고 이를 설명하시오.
[문제 분석]
방향과 차비가 있는 그래프에서 최저 비용 경로를 찾고 자동화 알고리즘을 설명하는 문제입니다.
[예시답안 요약 힌트]
가능한 경로의 비용을 비교하고, 경로·차비 변수를 두어 모든 경로를 탐색한 뒤 최솟값을 출력하는 절차를 쓰세요.
최저 비용 경로를 자동으로 구하는 알고리즘 (다익스트라 알고리즘):
① 출발 도시(㉮)의 거리를 0으로, 나머지 도시는 무한대(∞)로 초기화한다.
② 방문하지 않은 도시 중 거리가 가장 작은 도시를 선택한다.
③ 선택한 도시에서 이동 가능한 다음 도시의 거리를 갱신한다.
(현재 도시까지 거리 + 다음 도시까지 차비 < 기존 기록 → 업데이트)
④ 모든 도시를 방문할 때까지 ②~③을 반복한다.
⑤ 도착 도시(㉯)에 저장된 값이 최저 비용이다.
이 알고리즘을 사용하면 경로 수에 관계없이 항상 최저 비용을 자동으로 찾을 수 있다.
정답을 외우기보다 글·표·그림 배치를 비교하며 내 답안을 보완하세요.
3-2 예시답안 1
로그인 후 답안을 작성할 수 있습니다.