다음은 우리나라의 주요 도시들을 연결하는 초고속철도를 건설하기 위한 지… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
다음은 우리나라의 주요 도시들을 연결하는 초고속철도를 건설하기 위한 지도를 그래프로 표현한 것이다. 최소비용 신장 트리를 구하는 Kruskal 알고리즘을 이용하여 초고속철도를 건설하려고 한다. 4번째로 건설해야 할 구간은?
문제 이미지
1
포항 ↔ 부산
2
진주 ↔ 부산
3
서울 ↔ 인천
4
인천 ↔ 목포
해설

Kruskal 알고리즘에서 네 번째로 건설할 구간은 인천 ↔ 목포이다.

Kruskal은 간선을 가중치 오름차순으로 정렬해 사이클을 만들지 않는 가장 가벼운 간선부터 고른다. 순서는 포항–부산 3, 서울–인천 4, 목포–진주 4, 인천–목포 7, 인천–진주 8 … 이다.

앞의 세 간선을 고른 뒤 인천–목포(가중치 7)는 서울·인천 묶음과 목포·진주 묶음을 잇는 간선이라 사이클이 생기지 않으므로 네 번째로 채택된다.

  • 포항 ↔ 부산은 가중치 3으로 가장 가벼워 첫 번째로 선택된다.
  • 서울 ↔ 인천은 가중치 4로 목포–진주와 함께 두 번째·세 번째로 선택된다.
  • 진주 ↔ 부산은 가중치 14로 가장 무거워, 그 차례가 오기 전에 진주와 부산이 이미 같은 트리로 이어져 사이클이 생기므로 신장 트리에 포함되지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 07년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기