방송대 방통대 이산수학 10강 - 그래프(II) - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 10강 - 그래프(II)

그래프를 교차 없이 그릴 수 있는지 판별하는 평면 그래프의 개념과 오일러 공식, 4색 정리를 학습한다. 이어서 모든 변을 한 번씩 지나는 오일러 투어와 모든 꼭지점을 한 번씩 지나는 해밀턴 경로를 구분하고, 가중 그래프에서 데이크스트라 알고리즘으로 최단 거리와 실제 경로를 구하는 과정을 이해한다.

1. 그래프 탐색과 활용의 학습 범위

10강은 앞 강의에서 배운 그래프의 기본 개념과 인접행렬 표현을 바탕으로 그래프의 구조를 탐색하고 실제 문제에 활용하는 방법을 다룬다. 강의 도입부에서는 영화 굿 윌 헌팅의 칠판 문제와 제9강 연습문제의 인접행렬 표현을 연결하여, 복잡한 그림도 꼭지점과 변의 관계로 분석할 수 있음을 보여 준다.

그래프 탐색 영역에서는 평면 그래프, 오일러 투어, 해밀턴 경로를 학습한다. 그래프 활용 영역에서는 변에 값이 부여된 가중 그래프와 출발지에서 목적지까지 가장 짧은 길을 찾는 최단 경로 문제를 다룬다.

영역	핵심 질문	주요 개념
평면 그래프	모든 변을 서로 교차하지 않게 그릴 수 있는가?	면, 오일러 공식, 4색 정리
오일러 투어	모든 변을 각각 한 번만 지나 출발점으로 돌아올 수 있는가?	차수, 연결성, 사이클 결합
해밀턴 경로	모든 꼭지점을 각각 한 번만 지날 수 있는가?	해밀턴 경로, 해밀턴 사이클
가중 그래프	변의 비용을 고려해 가장 짧은 경로를 어떻게 찾는가?	가중치, 최단 경로, 데이크스트라 알고리즘

2. 평면 그래프

평면 그래프의 정의

그래프의 모든 변을 서로 교차하지 않게 그릴 수 있으면 그 그래프를 평면 그래프(planar graph)라고 한다. 처음 제시된 그림에서 변이 교차하더라도 꼭지점과 변의 연결관계를 바꾸지 않은 채 다시 그려 교차를 없앨 수 있다면 평면 그래프이다. 따라서 평면성은 특정 그림의 모양이 아니라 그래프 자체의 성질이다.

강의는 평면 그래프가 아닌 예로 완전그래프 K₅, 완전이분그래프 K_3,3, Petersen 그래프를 제시한다. 반면 3-정규그래프와 완전그래프 K₄, K₅에서 한 변을 제거한 그래프는 평면적으로 다시 그릴 수 있는 예로 제시된다.

정규그래프와 완전그래프

정규그래프는 모든 꼭지점이 동일한 수의 인접한 꼭지점을 가지는 그래프이다. 완전그래프는 서로 다른 임의의 두 꼭지점 사이에 항상 변이 존재하는 그래프이다. K_n의 각 꼭지점은 나머지 n - 1개의 꼭지점과 인접하므로 K_n은 (n - 1)-정규그래프이다.

변이 교차해 보인다는 이유만으로 비평면 그래프라고 판단해서는 안 된다. 같은 인접관계를 유지하면서 변을 다시 배치하여 모든 교차를 제거할 수 있는지를 확인해야 한다.

3. 면과 오일러 공식

평면 그래프의 면

연결된 평면 그래프를 교차 없이 그렸을 때 변으로 둘러싸여 형성되는 공간을 면(face)이라고 한다. 닫힌 경계 안쪽의 공간뿐 아니라 그래프 바깥쪽으로 이어지는 외부 영역도 하나의 면으로 센다. 면의 수를 셀 때 외부 면을 빠뜨리지 않는 것이 중요하다.

오일러 공식

연결된 평면 그래프에서 꼭지점의 수를 v, 변의 수를 e, 면의 수를 f라고 하면 다음 식이 성립한다.

v - e + f = 2

예를 들어 연결된 평면 그래프의 꼭지점이 5개, 변이 7개라면 면의 수는 f = 2 - v + e = 2 - 5 + 7 = 4이다. 반대로 세 값 가운데 두 값을 알면 나머지 하나를 계산할 수 있다.

오일러 공식은 연결된 평면 그래프에 적용한다. 그림에서 면을 셀 때는 바깥 영역도 포함하며, 단순히 사이클의 개수와 면의 수를 같다고 생각해서는 안 된다.

4. 4색 정리

4색 정리는 지도의 서로 인접한 구역을 서로 다른 색으로 칠할 때 네 가지 색이면 충분하다는 정리이다. 지도에서 각 구역을 꼭지점으로, 경계를 맞댄 두 구역의 관계를 변으로 나타내면 평면 그래프의 꼭지점 색칠 문제로 바꿀 수 있다.

그래프 표현에서는 평면 그래프의 각 꼭지점을 색칠하되 인접한 두 꼭지점이 서로 다른 색을 갖도록 하는 데 네 가지 색이면 충분하다고 설명한다. 지도 색칠과 그래프 꼭지점 색칠은 표현 방식만 다를 뿐 같은 인접관계를 다룬다.

지도 표현	그래프 표현
하나의 구역	하나의 꼭지점
두 구역이 경계를 맞댐	두 꼭지점이 변으로 인접함
인접 구역을 다른 색으로 칠함	인접 꼭지점에 다른 색을 지정함
네 가지 색이면 충분함	평면 그래프의 꼭지점 색칠에 네 색이면 충분함

5. 오일러 트레일과 오일러 투어

정의와 관련 용어

오일러 트레일(Eulerian trail)은 그래프의 모든 변을 각각 한 번만 지나는 트레일이다. 오일러 투어(Eulerian tour)는 시작점과 종점이 같은 닫힌 오일러 트레일이다. 모든 변을 한 번씩 사용하고 출발한 꼭지점으로 돌아와야 한다.

용어	핵심 조건
워크	꼭지점과 변을 따라 이동하는 일반적인 열
트레일	사용하는 모든 변이 서로 다른 워크
경로	모든 꼭지점이 서로 다른 트레일
투어	그래프의 모든 변을 포함한 닫힌 워크
사이클	시작점과 종점이 같은 닫힌 경로

오일러 그래프 정리

연결 그래프가 오일러 투어를 가질 필요충분조건은 모든 꼭지점의 차수가 짝수인 것이다. 오일러 투어가 존재하면 한 꼭지점으로 들어오는 변과 나가는 변이 쌍을 이루므로 모든 꼭지점의 차수는 짝수이다.

반대로 연결 그래프의 모든 꼭지점 차수가 짝수이면 임의의 꼭지점에서 출발하여 닫힌 사이클을 만들 수 있다. 아직 사용하지 않은 변이 남아 있으면 기존 사이클과 남은 그래프가 공유하는 꼭지점에서 새로운 사이클을 만든 뒤 기존 사이클에 끼워 넣는다. 이 과정을 모든 변이 포함될 때까지 반복하면 오일러 투어를 얻는다.

오일러 투어 구성 절차

1. 그래프 G에서 임의의 꼭지점 v를 고른다.
2. v에서 시작하여 v에서 끝나는 임의의 사이클 C를 선택한다.
3. C가 모든 변을 포함하면 C가 오일러 투어이므로 끝낸다.
4. 아니라면 G에서 C에 속한 변을 제거하여 G′을 만든다.
5. C와 G′이 공유하는 꼭지점 w를 선택하고, w에서 시작하고 끝나는 새 사이클 C′을 만든다.
6. C에 C′을 결합하고 모든 변이 포함될 때까지 반복한다.

오일러 투어는 꼭지점의 반복 방문을 허용하지만 각 변은 정확히 한 번만 사용한다. 존재 여부를 판단할 때는 그래프의 연결성과 모든 꼭지점 차수의 짝수 여부를 확인한다.

6. 해밀턴 경로와 해밀턴 사이클

해밀턴 경로(Hamiltonian path)는 그래프의 모든 꼭지점을 각각 한 번씩만 지나는 경로이다. 해밀턴 사이클(Hamiltonian cycle)은 시작점과 종점이 같은 닫힌 해밀턴 경로이다.

오일러 문제와 해밀턴 문제는 기준이 다르다. 오일러는 모든 변을 한 번씩 사용하는지에 관심을 두고, 해밀턴은 모든 꼭지점을 한 번씩 방문하는지에 관심을 둔다. 따라서 오일러 투어가 존재한다고 해서 해밀턴 사이클도 반드시 존재하는 것은 아니며, 그 반대도 보장되지 않는다.

구분	오일러 트레일·투어	해밀턴 경로·사이클
핵심 대상	모든 변	모든 꼭지점
한 번만 사용	각 변을 한 번만 사용	각 꼭지점을 한 번만 방문
닫힌 형태	오일러 투어	해밀턴 사이클
대표 판정 관점	연결성과 꼭지점의 차수	가능한 꼭지점 방문 순서를 탐색

강의는 여러 그래프와 12면체 그래프, Herschel 그래프의 그림에서 해밀턴 경로와 사이클을 탐색하는 예를 제시한다. 그림을 볼 때 모든 꼭지점을 빠짐없이 한 번씩 포함했는지, 닫힌 형태라면 마지막 꼭지점에서 처음 꼭지점으로 돌아오는 변이 존재하는지를 확인해야 한다.

“한 번씩”의 대상이 변인지 꼭지점인지가 가장 중요한 구분 기준이다. 오일러 투어에서는 꼭지점을 다시 지나도 되지만 변을 반복할 수 없고, 해밀턴 경로에서는 모든 꼭지점을 한 번씩만 방문해야 한다.

7. 가중 그래프와 최적화 문제

가중 그래프

가중 그래프(weighted graph)는 각 변에 실수값이 붙어 있는 그래프이다. 변에 부여된 값을 가중치(weight)라고 한다. 가중치는 도로의 거리, 이동 시간, 비용 등 문제에서 비교하려는 값을 나타낼 수 있다.

최단 경로 문제

최단 경로 문제는 출발지와 도착지가 주어졌을 때 두 지점을 잇는 경로 가운데 가중치의 합이 가장 작은 경로를 찾는 문제이다. 단순히 지나가는 변의 개수가 적은 경로가 아니라 각 변의 가중치를 합한 값이 최소인 경로를 찾아야 한다.

최소 신장 트리 문제

트리는 사이클이 없는 연결 그래프이다. 그래프 G = (V, E)의 모든 꼭지점을 연결하면서 사이클이 없는 부분 그래프를 G의 신장 트리라고 한다. 가중 그래프의 신장 트리 가운데 모든 변의 가중치 합이 가장 작은 것을 최소 신장 트리라고 한다.

문제	목표	결과
최단 경로	지정된 출발지에서 목적지까지 가중치 합 최소화	두 지점 사이의 하나의 경로
최소 신장 트리	모든 꼭지점을 연결하면서 전체 가중치 합 최소화	사이클이 없는 신장 트리

최단 경로는 특정 두 지점 사이의 이동을 최적화하고, 최소 신장 트리는 그래프의 모든 꼭지점을 연결하는 전체 구조를 최적화한다.

8. 데이크스트라 최단 경로 알고리즘

거리 배열과 미확정 꼭지점 집합

데이크스트라(Dijkstra) 알고리즘은 출발점 s에서 각 꼭지점까지 알려진 최단 거리의 추정값 d[v]를 관리한다. 처음에는 모든 d[v]를 ∞로 설정하고 출발점의 값만 d[s] = 0으로 둔다. 아직 처리를 마치지 않은 모든 꼭지점은 집합 Q에 넣는다.

최솟값 선택과 이완

Q가 빌 때까지 d[u]가 가장 작은 꼭지점 u를 선택하여 Q에서 제거한다. 그런 다음 Q에 남아 있으면서 u와 인접한 각 꼭지점 v에 대해 다음 갱신을 수행한다.

d[v] ← min(d[v], d[u] + w(u, v))

현재 알고 있는 d[v]보다 u를 거쳐 가는 거리 d[u] + w(u, v)가 짧으면 d[v]를 새 값으로 바꾼다. 이 과정을 이완이라고 이해할 수 있다. 더 짧지 않으면 기존 값을 그대로 유지한다.

1. 모든 꼭지점 v에 대해 d[v] = ∞로 초기화한다.
2. 출발점 s에 대해 d[s] = 0으로 설정한다.
3. 모든 꼭지점을 미확정 집합 Q에 넣는다.
4. Q에서 d 값이 가장 작은 꼭지점 u를 선택한다.
5. u를 Q에서 제거하고, Q에 남은 u의 인접 꼭지점들의 거리를 이완한다.
6. Q가 빌 때까지 4~5단계를 반복한다.

9. 데이크스트라 예제와 경로 복원

거리 갱신 과정

강의 예제는 꼭지점 a를 출발점으로 삼는다. 초기에는 d[a] = 0이고 나머지 꼭지점 b, c, d, e, f의 거리는 모두 ∞이다. a를 선택한 뒤 인접 꼭지점을 이완하면 d[b] = 2, d[e] = 4가 된다.

다음으로 최솟값을 가진 b를 선택하면 d[c] = 3, d[d] = 7, d[e] = 4, d[f] = 4가 된다. 이어서 c를 선택하면 c를 거쳐 d로 가는 거리가 3 + 3 = 6이므로 기존 d[d] = 7이 6으로 갱신된다. 이후 후보를 처리하면 최종 거리는 다음과 같다.

꼭지점	a에서의 최단 거리	최단 경로의 이전 꼭지점
a	0	없음
b	2	a
c	3	b
d	6	c
e	4	a
f	4	b

prev 배열을 이용한 경로 복원

최단 거리만이 아니라 실제 경로를 얻으려면 더 짧은 거리로 갱신할 때 prev[v]에 이전 꼭지점 u를 저장한다. 목적지 t에서 시작하여 prev를 거꾸로 따라가며 각 꼭지점을 경로 P의 맨 앞에 삽입하면 출발지부터 목적지까지의 순서를 복원할 수 있다.

a에서 d까지의 경로를 구하면 먼저 P = [d]이고 prev[d] = c이므로 [c, d], prev[c] = b이므로 [b, c, d], prev[b] = a이므로 [a, b, c, d]가 된다. 따라서 최단 경로는 a → b → c → d이고 총 가중치는 2 + 1 + 3 = 6이다.

거리 d[v]는 출발점에서 v까지의 최단 거리값을 저장하고, prev[v]는 그 최단 경로에서 v 바로 앞의 꼭지점을 저장한다. 두 배열의 역할을 혼동하지 않아야 한다.

핵심 개념 정리

• 평면 그래프는 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프이며, 그림을 다시 그려 교차를 제거할 수 있는지도 확인해야 한다.
• 연결된 평면 그래프에서는 꼭지점 수 v, 변 수 e, 면 수 f에 대해 v - e + f = 2가 성립한다.
• 4색 정리는 평면 그래프의 인접 꼭지점에 서로 다른 색을 지정할 때 네 가지 색이면 충분하다는 정리이다.
• 오일러 트레일은 모든 변을 한 번씩 지나는 트레일이고, 오일러 투어는 시작점과 종점이 같은 오일러 트레일이다.
• 연결 그래프가 오일러 투어를 가질 필요충분조건은 모든 꼭지점의 차수가 짝수인 것이다.
• 해밀턴 경로는 모든 꼭지점을 한 번씩 지나는 경로이고, 해밀턴 사이클은 닫힌 해밀턴 경로이다.
• 오일러 문제는 변의 사용에, 해밀턴 문제는 꼭지점의 방문에 초점을 둔다.
• 가중 그래프는 각 변에 실수값인 가중치가 붙은 그래프이다.
• 최단 경로는 두 지점 사이의 가중치 합을 최소화하고, 최소 신장 트리는 모든 꼭지점을 연결하는 전체 가중치 합을 최소화한다.
• 데이크스트라 알고리즘은 가장 작은 잠정 거리의 꼭지점을 선택하고 d[v] = min(d[v], d[u] + w(u, v))로 인접 꼭지점의 거리를 갱신한다.
• prev 배열을 목적지에서 출발지 방향으로 따라가면 실제 최단 경로를 복원할 수 있다.

그래프 탐색 문제에서는 무엇을 한 번씩 다루는지 먼저 구분해야 한다. 평면 그래프는 변의 교차 가능성, 오일러 투어는 모든 변, 해밀턴 경로는 모든 꼭지점, 최단 경로는 변의 가중치 합을 기준으로 판단한다.

예상문제 20선

1. 평면 그래프의 정의로 옳은 것은?

① 모든 꼭지점의 차수가 같은 그래프 ② 모든 꼭지점 쌍 사이에 변이 있는 그래프 ③ 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프 ④ 모든 변의 가중치가 같은 그래프

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
평면 그래프는 인접관계를 바꾸지 않고 다시 그렸을 때 모든 변의 교차를 제거할 수 있는 그래프이다.

2. 강의에서 평면 그래프가 아닌 예로 제시된 것은?

① K₅ ② K₄ ③ K₅에서 한 변을 제거한 그래프 ④ 강의에 제시된 3-정규 평면 그래프

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
강의는 K₅, K_3,3, Petersen 그래프를 비평면 그래프의 예로 제시한다.

3. 완전그래프 K_n의 정규성에 대한 설명으로 옳은 것은?

① n-정규그래프이다. ② 1-정규그래프이다. ③ 정규그래프가 될 수 없다. ④ (n - 1)-정규그래프이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
K_n의 각 꼭지점은 자신을 제외한 n - 1개의 모든 꼭지점과 인접하므로 차수가 n - 1이다.

4. 연결된 평면 그래프에서 v = 6, e = 9일 때 면의 수 f는?

① 3 ② 5 ③ 7 ④ 17

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
v - e + f = 2에 대입하면 6 - 9 + f = 2이므로 f = 5이다. 외부 면도 포함한 값이다.

5. 평면 그래프의 면을 셀 때 유의할 점으로 옳은 것은?

① 꼭지점만 세고 변은 무시한다. ② 모든 사이클을 각각 두 개의 면으로 센다. ③ 그래프 바깥쪽의 외부 영역도 하나의 면으로 센다. ④ 변이 없는 영역만 면으로 센다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
평면 그래프에서 변으로 구분되는 바깥쪽 공간도 하나의 면이므로 반드시 포함해야 한다.

6. 4색 정리에 대한 설명으로 옳은 것은?

① 모든 그래프의 변을 네 개만 남기면 충분하다는 정리이다. ② 평면 그래프의 인접 꼭지점을 다른 색으로 칠하는 데 네 색이면 충분하다. ③ 평면 그래프에는 꼭지점이 최대 네 개만 존재한다. ④ 모든 인접 꼭지점을 같은 색으로 칠해야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
지도 구역을 꼭지점으로 바꾸면 4색 정리는 평면 그래프의 인접 꼭지점 색칠 문제로 표현할 수 있다.

7. 오일러 트레일의 정의는?

① 그래프의 모든 변을 각각 한 번만 지나는 트레일 ② 모든 꼭지점을 반드시 두 번 지나는 워크 ③ 가중치가 가장 큰 변만 지나는 경로 ④ 모든 면을 한 번씩 색칠하는 과정

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
오일러 트레일의 기준은 그래프의 모든 변이며, 각 변을 정확히 한 번만 사용한다.

8. 오일러 투어가 오일러 트레일과 구별되는 조건은?

① 꼭지점을 전혀 방문하지 않는다. ② 변을 반복해서 사용한다. ③ 모든 변에 같은 가중치가 있다. ④ 시작점과 종점이 같다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
오일러 투어는 닫힌 오일러 트레일이므로 모든 변을 한 번씩 지나고 출발점으로 돌아온다.

9. 연결 그래프가 오일러 투어를 가질 필요충분조건은?

① 모든 꼭지점의 차수가 짝수이다. ② 모든 꼭지점의 차수가 홀수이다. ③ 꼭지점이 정확히 네 개이다. ④ 모든 변의 가중치가 0이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
연결성과 모든 꼭지점 차수의 짝수성이 오일러 투어 존재의 필요충분조건이다.

10. 오일러 투어 구성 알고리즘에서 사용하지 않은 변이 남아 있을 때의 처리로 옳은 것은?

① 기존 사이클의 모든 꼭지점을 삭제한다. ② 남은 변의 가중치를 모두 0으로 만든다. ③ 공유 꼭지점에서 새 사이클을 만들고 기존 사이클에 결합한다. ④ 그래프의 연결 여부와 무관하게 즉시 종료한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
기존 사이클과 남은 그래프가 공유하는 꼭지점에서 새 사이클을 만든 뒤 끼워 넣는 과정을 반복한다.

11. 해밀턴 경로의 정의로 옳은 것은?

① 모든 변을 두 번씩 지나는 닫힌 워크 ② 그래프의 모든 꼭지점을 각각 한 번씩 지나는 경로 ③ 가장 큰 가중치의 변만 선택한 트리 ④ 모든 면을 지나는 오일러 투어

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
해밀턴 경로는 변이 아니라 꼭지점의 방문에 초점을 두며 모든 꼭지점을 한 번씩 포함한다.

12. 오일러 투어와 해밀턴 사이클의 비교로 옳은 것은?

① 둘 다 모든 변을 한 번씩만 사용하는 개념이다. ② 둘 다 모든 꼭지점의 차수가 짝수여야만 한다. ③ 오일러는 꼭지점, 해밀턴은 면을 기준으로 한다. ④ 오일러는 모든 변, 해밀턴은 모든 꼭지점을 기준으로 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
오일러 문제에서 한 번씩 사용해야 하는 대상은 변이고, 해밀턴 문제에서는 꼭지점이다.

13. 가중 그래프에 대한 설명으로 옳은 것은?

① 모든 꼭지점에만 색이 지정된 그래프이다. ② 모든 꼭지점의 차수가 같은 그래프이다. ③ 변이 하나도 없는 그래프이다. ④ 각 변에 실수값인 가중치가 부여된 그래프이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
가중 그래프에서는 각 변에 거리, 시간, 비용 등을 나타낼 수 있는 실수값이 붙는다.

14. 최단 경로 문제와 최소 신장 트리 문제의 차이로 옳은 것은?

① 최단 경로는 두 지점 사이를, 최소 신장 트리는 모든 꼭지점의 연결을 최적화한다. ② 두 문제 모두 반드시 하나의 변만 선택한다. ③ 최소 신장 트리는 사이클을 반드시 포함한다. ④ 최단 경로는 가중치를 고려하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
최단 경로는 지정된 출발지와 목적지 사이의 경로를 찾고, 최소 신장 트리는 그래프의 모든 꼭지점을 최소 총 가중치로 연결한다.

15. 데이크스트라 알고리즘의 초기화로 옳은 것은?

① 모든 d[v]를 0으로 둔다. ② 모든 d[v]를 ∞로 두고 출발점 d[s]만 0으로 둔다. ③ 출발점 d[s]를 ∞로 두고 나머지만 0으로 둔다. ④ 모든 꼭지점을 Q에서 제거하고 시작한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
아직 경로를 모르는 꼭지점의 거리는 ∞로 초기화하고, 출발점에서 자신까지의 거리는 0으로 설정한다.

16. 데이크스트라 알고리즘에서 다음에 처리할 꼭지점 u를 선택하는 기준은?

① Q에서 차수가 가장 큰 꼭지점 ② Q에서 이름이 가장 빠른 꼭지점 ③ Q에서 잠정 거리 d[u]가 가장 작은 꼭지점 ④ 이미 Q에서 제거된 꼭지점

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
미확정 집합 Q에 남은 꼭지점 가운데 현재 d 값이 최소인 u를 선택한 뒤 인접 꼭지점을 이완한다.

17. 거리 이완식으로 옳은 것은?

① d[v] ← min(d[v], d[u] + w(u, v)) ② d[v] ← max(d[v], d[u] + w(u, v)) ③ d[v] ← d[v] + d[u] + w(u, v) ④ d[v] ← w(u, v)만 사용

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
기존 거리와 u를 거쳐 가는 새 거리 중 더 작은 값을 d[v]로 선택한다.

18. 강의 예제에서 a를 출발점으로 할 때 최종 d[d]의 값은?

① 3 ② 4 ③ 7 ④ 6

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
b를 처리한 뒤 d[d]는 7이지만, c를 거치면 3 + 3 = 6이 되어 더 짧은 값으로 갱신된다.

19. 데이크스트라 알고리즘에서 prev[v]의 역할은?

① 꼭지점 v의 차수를 저장한다. ② 꼭지점 v가 만드는 면의 수를 저장한다. ③ 최단 경로에서 v 바로 앞의 꼭지점을 저장한다. ④ 사용하지 않은 색의 수를 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
더 짧은 경로로 거리값을 갱신할 때 이전 꼭지점을 prev에 기록하면 목적지에서 역추적하여 실제 경로를 복원할 수 있다.

20. 강의 예제에서 a에서 d까지 복원한 최단 경로는?

① a → e → f → d ② a → b → c → d ③ a → c → b → d ④ a → d

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
prev[d] = c, prev[c] = b, prev[b] = a를 역순으로 따라가면 a → b → c → d이며 총 가중치는 6이다.