다음은 우리나라의 주요 도시들을 연결하는 초고속철도를 건설하기 위한 지… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
다음은 우리나라의 주요 도시들을 연결하는 초고속철도를 건설하기 위한 지도를 그래프로 표현한 것이다. 최소비용 신장 트리를 구하는 Kruskal 알고리즘을 이용하여 초고속철도를 건설하려고 한다. 4번째로 건설해야 할 구간은?
1
포항 ↔ 부산
2
진주 ↔ 부산
3
서울 ↔ 인천
4
인천 ↔ 목포
해설
Kruskal 알고리즘에서 네 번째로 건설할 구간은 인천 ↔ 목포이다.
Kruskal은 간선을 가중치 오름차순으로 정렬해 사이클을 만들지 않는 가장 가벼운 간선부터 고른다. 순서는 포항–부산 3, 서울–인천 4, 목포–진주 4, 인천–목포 7, 인천–진주 8 … 이다.
앞의 세 간선을 고른 뒤 인천–목포(가중치 7)는 서울·인천 묶음과 목포·진주 묶음을 잇는 간선이라 사이클이 생기지 않으므로 네 번째로 채택된다.
- 포항 ↔ 부산은 가중치 3으로 가장 가벼워 첫 번째로 선택된다.
- 서울 ↔ 인천은 가중치 4로 목포–진주와 함께 두 번째·세 번째로 선택된다.
- 진주 ↔ 부산은 가중치 14로 가장 무거워, 그 차례가 오기 전에 진주와 부산이 이미 같은 트리로 이어져 사이클이 생기므로 신장 트리에 포함되지 않는다.
오류나 개정된 내용이 보이면 알려주세요
