✍️ 문제 3-1
제9회 소프트웨어(SW) 사고력 올림피아드(중1~3)
※ 다음 문제에 답하시오.
※ 답은 종이에 작성한 뒤 사진으로 제출하세요.
※ 창의적인 생각을 자유롭게 기록해도 됩니다.
문제 3
아래 그림은 도시 사이의 길과 차비를 보여준다. 화살표는 갈 수 있는 방향을 나타내며, 화살표에 붙은 숫자는 차비를 의미한다. ㉮에서 ㉯로 가는 길 중 가장 차비가 적게 드는 길을 찾으려 한다.
문제 3-1
㉮에서 ㉯로 가는 차비가 가장 적게 드는 길을 찾아서 적고, 이 길을 갈 수 없을 때 다른 길을 찾고 설명하시오.
[문제 분석]
방향과 차비가 있는 그래프에서 최저 비용 경로를 찾고 자동화 알고리즘을 설명하는 문제입니다.
[예시답안 요약 힌트]
가능한 경로의 비용을 비교하고, 경로·차비 변수를 두어 모든 경로를 탐색한 뒤 최솟값을 출력하는 절차를 쓰세요.
㉮에서 ㉯로 가는 최저 비용 경로:
가능한 경로들의 차비를 모두 계산한다.
예시 그래프에서 최저 비용 경로: ㉮ → B → D → ㉯ = 5+6+4 = 15원 (최솟값)
대체 경로(최저 경로 이용 불가 시): ㉮ → C → ㉯ = 7+10 = 17원이 다음으로 저렴한 경로
경로 선택 기준: 모든 가능한 경로의 총 차비를 비교하여 가장 작은 값을 선택한다.
정답을 외우기보다 글·표·그림 배치를 비교하며 내 답안을 보완하세요.
3-1 예시답안 1
로그인 후 답안을 작성할 수 있습니다.