1. 알고리즘(30점)
<문제>
제시된 [그림]은 최소비용 그래프 G의 각 정점에 연결된 N-1개의 간선들의 가중치를 모두 합하여 정점1에서 N까지 이동에 소요되는 총 가중치의 합을 출력하는 순서도이다. <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항 보기>에서 선택하여 해당 번호 (1)~(5)에 마크하시오.
정점 1에서 N까지 이동하는 가중치 그래프 G가 있다.
정점 1에서 N까지 이동하는 가중치 그래프 G의 모든 간선의 개수는 X이며, 모든 간선에는 가중치가 주어져 있다. 각 간선들이 가중치를 정점과 정점 사이의 이동에 필요한 소요비용이라고 할 때. N개의 정점들에 연결된 총 K개의 간선의 가중치 Selection Sort를 이용하여 오름차순 정렬하고 정렬되어 있는 순서대로 가장 가중치가 작은 간선부터 사이클 없이 N-1개를 삽입하여 연결하면 최소비용 그래프 G를 완성할 수 있다.
<처리조건>
1. 그림의 순서도에 제시되어있는 미완성 알고리즘을 분석하여, 가장 적합한 로직으로 연계되어 구현될 수 있도록 답안 설계 시 유의하시오.
2. 정점의 개수는 N이고, 간선의 총 개수는 X이다.(단, N>5, X>7)
3. 배열 "Cost(X)"는 X개의 각 간선들의 가중치 값이 저장된다고 가정한다. (단, 가중치 값 중 동일 값은 없다고 가정한다.)
4. 배열 "Cycle(X)"은 X개의 각 간선들 삽입에 따른 그래프의 사이클 여부를 체크한 값이 저장되어 있는 배열로서 간선 삽입 시 사이클이 형성될 경우는 1, 형성되지 않을 경우는 0의 값이 자동적으로 저장되어 있다고 가정한다.
<순서도>
<답항보기>
|
1
|
K=X-1
|
2
|
K=i+j
|
3
|
i+1
|
4
|
Cost(j)=Cost(i)
|
5
|
L=TEMP+K
|
|
6
|
COT(i)
|
7
|
X=X+1
|
8
|
Min_Tot=K+L
|
9
|
K=L-1
|
10
|
i+X
|
|
11
|
Cost(K)=Cost(j)
|
12
|
Cost(N)
|
13
|
K+1
|
14
|
L=Cost(i)+Cost(j)
|
15
|
L=L+1
|
|
16
|
Cost(i)=Cost(j)
|
17
|
Cost(N)
|
18
|
K+1
|
19
|
L=Cost(i)+Cost(j)
|
20
|
Cost(K+L)
|
|
21
|
L=K+1
|
22
|
X
|
23
|
L=i+j
|
24
|
Cost(i)=Cost(j)
|
25
|
Cost(X)
|
|
26
|
N
|
27
|
Cycle(K)=i+j
|
28
|
Min_Tot=i+j
|
29
|
K=Cost(i)+Cost(j)
|
30
|
K=K+1
|
|
31
|
Cost(i)=Cost(K)
|
32
|
K=N+X
|
33
|
COSR(i+j)
|
34
|
Cost(j)
|
35
|
TEMP+1
|
|
36
|
i+N
|
37
|
Cycle(X)
|
38
|
Cost(K)
|
39
|
i+2
|
40
|
X+1
|
<정답>
1. i + 1
2. Cost(i) = Cost(j)
3. Cost(K)
4. L = L + 1
5. K = K + 1
<순서도 정답>
<설명>
(1) 아래 그래프를 C#언어로 표현하고자 한다. 7개의 노드가 있고, 11개의 간선이 있고, 각각의 간선에는 가중치가 구성되어져 있다.
이 그래프를 Cost 배열과 Cycle 배열로 표현해 놓은 자료가 아래에 제시하는 C# 코드의 16, 17번 라인이다.
(2) 직관적으로 표현해서 가중치가 작은것을 기준으로 최적 경로를 구해보면, 아래 빨간색 테두리를 갖는 간선이 최적경로이다. 빨간색 간선을 모두 더해보면, 29의 값을 갖는다.
(3) 위 그래프를 C# 코드로 옮겨 본 자료는 아래와 같다.
위 코드의 22번 라인은 전형적인 Selection Sort의 기본 코드이다. 이는 정보처리 실기 시험에 자주 출제되는 핵심 구문이기도 하다.
(4) 실행 결과이다.
끝.