확률과 통계순열과 조합수능 기출기본 문제 (3점 중반)

철도 최소 생성수형도

문제

건설교통부에서는 $\mathrm{A} , B , C , D , E$ 의 $5$ 개의 도시를 연결하는 철도를 새로 건설할 계획을 가지고 있다. 다음 표는 두 도시를 직접 연결하는 철도를 건설하는데 드는 비용을 간단한 정수비로 나타낸 것이다. 건설 비용은 가능하면 적게 들이면서 $5$ 개의 도시가 모두 연결되도록 철도를 건설하려고 할 때, $\mathrm{A}$ 와 직접 연결되는 도시를 모두 적은 것은? [3점]

	$\mathrm{A}$	$\mathrm{B}$	$\mathrm{C}$	$\mathrm{D}$	$\mathrm{E}$
$\mathrm{A}$		$6$	$5$	$7$	$2$
$\mathrm{B}$	$6$		$5$	$8$	$6$
$\mathrm{C}$	$5$	$5$		$9$	4
$\mathrm{D}$	$7$	$8$	$9$		$8$
$\mathrm{E}$	$2$	$6$	4	$8$

① $\mathrm{B}$ ② $\mathrm{C}$ ③ $\mathrm{B}$ , $\mathrm{E}$ ④ $\mathrm{C}$ , $\mathrm{D}$ ⑤ $\mathrm{D}$ , $\mathrm{E}$

정답 보기

⑤

자료 내려받기

아직 올라온 파일이 없습니다.

해설

표를 그래프로 나타내면 그림과 같다. 다음과 같은 방법으로 건설비용의 최소값을 찾을 수 있다. ㉠ 먼저 $\mathrm{A}$ 를 선택하고 $\mathrm{A}$ 와 직접 연결된 변 중 최소값을 갖는 것을 선택한다. ∴ $\mathrm{A} - E$ ㉡ $\mathrm{A}$ 또는 $\mathrm{E}$ 와 연결된 변 중 최소값을 갖는 것을 선택한다. ∴ $\mathrm{A} - E - C$ ㉢ $\mathrm{A}$ 또는 $\mathrm{C}$ 와 연결된 변 중 최소값을 갖는 것을 선택한다. 단, 회로가 생기면 안 되므로 $\mathrm{A} - C$ 는 제외한다. ∴ $\mathrm{A} - E - C - B$ ㉣ $\mathrm{A}$ 또는 $\mathrm{B}$ 와 연결된 변 중 최소값을 갖는 것을 선택한다. 단, 회로가 생기면 안 되므로 $\mathrm{A} - C$ 와 $\mathrm{A} - B$ 는 제외한다. ∴ $\mathrm{D} - A - E - C - B$ ∴ $\mathrm{A}$ 와 직접 연결되는 도시는 $\mathrm{D}$ , $\mathrm{E}$ 이다.

← 전체 문제 목록으로

철도 최소 생성수형도

문제

자료 내려받기

해설

태그

비슷한 문제 더 보기