탐구 보고서에 근거와 판단을 담아 봅니다
- 대상·깊이
- 중학교 시작 · 고등학교 심화 중 선택
- 남길 결과물
- 탐구 보고서 · 가상 그래프 / 경로 비교표
- 시작 전
- 학교의 과제 안내와 선택할 원자료를 확인합니다.
- 준비물
- 가상 그래프 · 경로 비교표 · 아래 PDF 또는 Word 활동지
이 탐구에서 알아볼 것
비음수 가중치 그래프에서 최단 경로는 간선 가중치 합을 최소화하는 문제이며, 출발점과 목적지가 정해져야 한다.
나에게 맞는 깊이로 시작하기
중학교 · 시작
중학생은 교실이나 도시가 아닌 가상 장소 6개와 양수 거리 9개로 그래프를 만듭니다. 출발점에서 목적지까지 가능한 경로를 직접 나열해 각 변의 비용을 더하고, 이동 횟수 최소와 거리 합 최소가 다를 수 있음을 확인합니다.
고등학교 · 심화 방법 펼치기
고등학생은 가중치가 0 이상인 그래프에서 다익스트라 방식으로 아직 확정되지 않은 정점 중 현재 비용이 가장 작은 곳을 반복 선택합니다. 매 단계의 임시 거리와 이전 정점을 기록하고, 손으로 모든 경로를 나열한 결과와 비교해 알고리즘이 전제하는 조건을 설명합니다.
준비 순서
- 가상 장소 A~F와 양방향 연결선 9개를 만들고 연결선마다 양수 거리 단위를 붙입니다. 실제 학교 출입구·버스 노선·개인의 이동 데이터는 사용하지 않으며, 그래프가 가상이라고 표시합니다.
- 출발점에서 목적지까지 가능한 단순 경로를 적고 각 간선 가중치를 합산합니다. 간선이 적은 경로와 거리 합이 작은 경로를 따로 표시해 두 기준의 차이를 확인합니다.
- 고등 선택에서는 출발점 거리 0, 나머지는 무한대라고 놓고 가장 작은 임시 거리의 정점을 확정합니다. 이웃의 거리를 현재값과 새 경로값 중 작은 것으로 갱신하고, 표를 반복해 목적지의 최솟값과 경로를 복원합니다. 계산에서 음수 간선이 없다는 전제를 확인합니다.
자료에서 결론까지
- 주어진 자료
- 가상 그래프에 A-D 직접 경로는 11, A-B-D 경로는 4+8=12, A-C-D 경로는 6+3=9 거리 단위로 주어졌다고 하자. 이 세 경로만 비교한다.
- 살펴보는 과정
- 직접 경로는 이동 1번에 비용 11이고, A-C-D는 이동 2번에 비용 9다. 이동 횟수가 적은 경로가 반드시 거리 합도 가장 짧지는 않다.
- 도출한 결과
- 제시된 세 경로 중 A-C-D의 거리 합 9가 가장 작다고 쓴다. 전체 그래프의 최단 경로를 확정하려면 다른 경로도 확인해야 한다.
- 여기까지 알 수 있어요
- 경로와 수치는 가상이다. 실제 도로 거리·통행 시간·안전 경로를 나타내지 않는다.
완성도를 높이는 기준
학교의 공식 채점표가 아닌, 이 탐구를 스스로 점검하는 기준입니다.
| 살펴볼 기준 | 충분히 드러난 모습 | 더 보완할 모습 |
|---|---|---|
| 그래프 정의 | 정점·간선·가중치 단위와 출발·도착점을 명시한다. | 간선의 방향이나 비용 단위가 불명확하다. |
| 경로 계산 | 각 간선 합을 정확히 구하고 기준별 차이를 비교한다. | 이동 횟수와 가중치 합을 같은 값으로 처리한다. |
| 알고리즘 전제 | 비음수 가중치와 가상 자료 범위를 밝힌다. | 결과를 실제 이동 시간·안전성으로 확대 해석한다. |
표를 좌우로 밀어 나머지 내용을 확인하세요.
함께 쓸 보조 자료
- 가상 그래프: 정점 / 간선 / 양수 비용 / 단위
- 경로 비교표: 경로 순서 / 간선 비용 합 / 이동 횟수 / 선택 기준
아래 활동지에는 주제별 기록표와 탐구 보고서의 기본 구성 칸을 함께 담았습니다.
활동지 펼쳐 보기 ↗이 순서로 읽으면 도움이 됩니다
- 1. 추천 기준이 바뀌면 같은 입력도 다른 결과가 나올까?
정점·간선과 규칙을 표로 나타내어 단계별 계산을 기록한다.
- 2. 추천 기준이 바뀌면 같은 입력도 다른 결과가 나올까?
그래프 경로 계산을 입력·규칙·출력의 알고리즘으로 정리한다.
자료를 더 찾을 곳
- Cornell University CS 2110 · Shortest Paths ↗
lecture section “Weighted Graphs,” definition of non-negative edge weights and shortest path — 가중 그래프의 최단 경로는 간선 가중치 합을 최소화하는 경로이며 해당 다익스트라 설명은 비음수 가중치를 전제한다.
위 링크는 자료를 탐색하는 출발점입니다. 제출물에는 실제로 읽은 개별 자료의 제목·작성자·발행일·주소·확인한 위치를 적어 주세요.
질문을 한 걸음 더 넓히면
가상 그래프에 지름길 간선을 하나 추가하고 최단 경로가 바뀌는 조건과 새 경로 비용을 계산한다.
제출 전에 스스로 점검하기
- □ 간선 가중치를 합산하고 비용 단위를 일관되게 썼나요?
- □ 최소 거리와 실제 이동 시간·접근성·안전을 혼동하지 않았나요?
- □ 학교의 안내문에 나온 분량·형식·평가 기준·AI 사용 조건을 확인했나요?
- □ 도움을 받은 부분과 내가 조사·해석·수정한 과정을 구별했나요?
독자용 주제 분류입니다. 공식 과목명·개정 연도·성취기준은 별도 대조하며, 아래 활동은 성취기준 인증 자료가 아닙니다.