방송대 자료구조 15강 : 그래프 탐색과 최소 비용 신장 트리

방송대 자료구조 15강: 그래프 탐색과 최소 비용 신장 트리

같은 그래프를 보더라도 모든 정점을 어떤 순서로 방문할 것인지와 모든 정점을 가장 적은 비용으로 연결할 것인지는 서로 다른 문제입니다. 이 글은 DFS·BFS의 프런티어 변화와 Prim·Kruskal·Sollin 알고리즘의 간선 선택 과정을 직접 추적해, 어떤 자료구조와 판정 규칙이 필요한지 구분하도록 돕습니다.

그래프 문제는 방문할 것인지 연결할 것인지부터 갈린다

정점과 간선이 주어졌을 때 먼저 확인할 것은 출력으로 무엇을 원하는가입니다. 그래프 탐색은 시작 정점에서 도달 가능한 정점을 빠짐없이 한 번씩 방문하는 순서를 만듭니다. 반면 신장 트리는 원래 그래프의 모든 정점을 포함하면서 사이클이 없는 연결 구조를 고릅니다. 간선에 비용이 있다면 그중 총비용이 가장 작은 구조가 최소 비용 신장 트리입니다.

판단 질문	주요 결과	핵심 상태	대표 방법
다음에 어느 정점을 방문할까?	정점 방문 순서와 탐색 신장 트리	방문 여부, 아직 처리할 정점	DFS, BFS
어느 간선을 남겨 모두 연결할까?	간선이 n-1개인 신장 트리	연결된 정점 집합 또는 여러 트리	Prim, Kruskal, Sollin
비용까지 최소화하려면?	총 가중치가 최소인 신장 트리	후보 간선의 비용과 사이클 여부	세 최소 비용 신장 트리 알고리즘

탐색 순서만 필요한데 간선 비용부터 비교하거나, 최소 비용 연결이 필요한데 DFS 방문 순서만 구하면 문제의 목표가 어긋납니다. 이후의 모든 알고리즘은 ‘정점 방문’과 ‘간선 선택’ 가운데 무엇을 결정하는지에 따라 읽어야 합니다.

DFS는 막다른 곳에서 가장 최근 갈림길로 돌아간다

깊이 우선 탐색(Depth First Search, DFS)은 시작 정점을 방문한 뒤, 그 정점에 인접한 미방문 정점 하나를 골라 가능한 한 깊이 내려갑니다. 현재 정점에 더 갈 곳이 없으면 가장 최근에 선택했던 정점으로 되돌아가 다른 간선을 확인합니다. ‘가장 최근’이라는 복귀 규칙 때문에 재귀 호출의 호출 스택이나 명시적인 스택이 자연스럽게 대응합니다.

강의자료의 재귀형 흐름을 학습용 C 코드로 간결하게 다시 쓰면 다음과 같습니다. adj[v][w]는 v와 w의 인접 여부, visited[w]는 방문 여부를 나타낸다고 가정합니다.

void dfs(Graph *g, int v) {
    g->visited[v] = 1;
    printf("%d ", v);

    for (int w = 0; w < g->n; w++) {
        if (g->adj[v][w] && !g->visited[w]) {
            dfs(g, w);
        }
    }
}

함수에 들어오자마자 v를 방문 처리하는 이유가 중요합니다. 방문 표시가 늦으면 사이클을 따라 이미 처리 중인 정점으로 다시 들어갈 수 있습니다. 반복문은 정점 번호가 작은 순서로 인접 정점을 검사하므로, 같은 그래프라도 인접 정점을 저장한 순서가 바뀌면 방문 순서는 달라질 수 있지만 도달 가능한 정점을 빠짐없이 방문한다는 성질은 유지됩니다.

DFS 추적법: 현재 정점에서 미방문 이웃을 찾으면 즉시 내려가고, 없으면 스택의 직전 정점으로 돌아갑니다. 답안을 쓸 때는 방문 순서와 되돌아간 경로를 섞지 않습니다.

BFS는 먼저 발견한 정점의 이웃부터 차례로 넓힌다

너비 우선 탐색(Breadth First Search, BFS)은 시작 정점의 인접 정점을 먼저 모두 발견하고, 발견된 순서대로 각 정점의 미방문 이웃을 확장합니다. 먼저 들어온 정점을 먼저 꺼내는 큐를 사용하므로 시작점에서 한 간선 떨어진 정점, 두 간선 떨어진 정점처럼 층이 바깥으로 넓어집니다.

다음 코드는 강의자료의 배열 큐 흐름을 학습용으로 정리한 것입니다. 정점을 큐에 넣는 순간 방문 표시를 하여 같은 정점이 여러 번 큐에 들어가는 일을 막습니다.

void bfs(Graph *g, int start) {
    int queue[MAX_VERTICES];
    int front = 0;
    int rear = 0;

    for (int i = 0; i < g->n; i++) {
        g->visited[i] = 0;
    }

    g->visited[start] = 1;
    queue[rear++] = start;

    while (front < rear) {
        int v = queue[front++];
        printf("%d ", v);

        for (int w = 0; w < g->n; w++) {
            if (g->adj[v][w] && !g->visited[w]) {
                g->visited[w] = 1;
                queue[rear++] = w;
            }
        }
    }
}

front는 다음에 처리할 정점, rear는 새 정점을 넣을 위치를 가리킵니다. 큐에서 꺼낸 뒤 방문 표시를 하면 서로 다른 두 정점이 같은 미방문 이웃을 각각 큐에 넣을 수 있습니다. 따라서 ‘발견한 순간 표시, 처리할 때 꺼내기’가 중복을 막는 핵심 순서입니다.

같은 그래프도 스택과 큐에 따라 방문 순서가 달라진다

직접 구성한 연습 그래프를 생각해 봅시다. 무방향 간선은 A-B, A-C, B-D, B-E, C-F, E-F이며, 인접 정점은 알파벳순으로 선택한다고 가정합니다. 이 조건을 먼저 고정해야 방문 순서가 하나로 정해집니다.

단계	DFS의 현재 흐름	BFS에서 꺼낸 정점	BFS 큐의 남은 내용
시작	A 방문 후 B로 내려감	A	B, C
다음	B에서 D 방문 후 되돌아옴	B	C, D, E
확장	B에서 E, 이어서 F로 내려감	C	D, E, F
마무리	F에서 C를 방문하고 복귀	D, E, F 순서로 처리	빈 큐

따라서 DFS 방문 순서는 A-B-D-E-F-C, BFS 방문 순서는 A-B-C-D-E-F입니다. DFS가 남긴 탐색 간선은 A-B, B-D, B-E, E-F, F-C이고, BFS는 A-B, A-C, B-D, B-E, C-F를 남깁니다. 둘 다 모든 정점을 잇는 신장 트리를 만들지만 모양은 서로 다릅니다.

오개념 교정: DFS와 BFS의 방문 순서는 그래프만 보고 언제나 하나로 결정되는 값이 아닙니다. 여러 미방문 이웃 가운데 무엇을 먼저 고를지 규칙이 있어야 하며, 규칙이 달라져도 중복 없이 도달 가능한 정점을 모두 방문하면 올바른 탐색이 될 수 있습니다.

신장 트리는 모든 정점을 n-1개의 간선으로 연결한다

정점이 n개인 연결 그래프에서 신장 트리는 모든 정점을 포함하고 사이클이 없는 부분 그래프입니다. 트리는 두 정점 사이의 단순 경로가 하나뿐이므로 간선 수는 정확히 n-1개입니다. 간선이 그보다 적으면 모든 정점을 연결할 수 없고, 연결된 상태에서 하나 더 넣으면 사이클이 생깁니다.

DFS와 BFS가 선택한 탐색 간선도 신장 트리를 만들 수 있지만, 방문 순서를 정한 결과일 뿐 비용의 최소를 보장하지는 않습니다. 가중치 그래프에서는 가능한 신장 트리마다 간선 비용을 더하고, 총합이 가장 작은 것을 최소 비용 신장 트리라고 합니다.

완성 조건: 모든 정점이 하나로 연결되었는가, 선택 간선이 n-1개인가, 사이클이 없는가를 함께 확인합니다. 세 조건 가운데 하나만 확인해서는 신장 트리라고 판정할 수 없습니다.

Prim은 하나의 연결 영역을 바깥쪽으로 확장한다

Prim 알고리즘은 이미 포함된 정점 집합 W와 아직 포함되지 않은 정점을 잇는 간선 가운데 비용이 가장 작은 것을 골라, 하나의 트리를 계속 확장합니다. 강의자료의 흐름은 전체에서 가장 싼 간선으로 시작한 뒤 W의 정점과 바깥 정점을 연결하는 최소 간선을 반복 선택합니다.

직접 구성한 가중치 그래프에서 간선 비용을 B-C=1, A-C=2, D-E=2, A-B=4, B-D=5, B-E=7, C-D=8, C-E=10으로 둡시다. A에서 시작하면 다음과 같이 진행됩니다.

1. W={A}에서 바깥으로 나가는 A-C(2)와 A-B(4) 중 A-C를 고릅니다.
2. W={A,C}가 되면 경계 간선 중 B-C(1)가 가장 작으므로 B를 포함합니다.
3. W={A,B,C}에서 바깥으로 나가는 간선 중 B-D(5)를 골라 D를 포함합니다.
4. 이제 D-E(2)를 골라 E를 포함하면 모든 정점이 연결됩니다.

선택 간선은 A-C, B-C, B-D, D-E이고 총비용은 2+1+5+2=10입니다. 이미 W 안에 있는 두 정점을 잇는 A-B(4)는 값이 작아 보여도 새 정점을 추가하지 않으므로 후보에서 제외해야 합니다.

잘못된 선택: 매 단계마다 그래프 전체의 가장 싼 남은 간선만 고르면 Prim의 ‘현재 연결 영역을 확장한다’는 조건을 잃습니다. 후보는 반드시 W와 그 바깥을 가로지르는 간선이어야 합니다.

Kruskal은 싼 간선을 보되 서로 다른 성분만 합친다

Kruskal 알고리즘은 모든 간선을 비용 오름차순으로 살펴봅니다. 간선의 양 끝 정점이 현재 서로 다른 트리에 있으면 두 트리를 합치고, 이미 같은 트리에 있으면 사이클이 생기므로 건너뜁니다. 중간 결과가 하나의 트리일 필요는 없으며 여러 개의 분리된 트리, 즉 숲일 수 있습니다.

앞의 직접 구성한 그래프에서는 B-C(1), A-C(2), D-E(2)를 먼저 고릅니다. 다음 A-B(4)는 A와 B가 이미 A-C-B로 연결되어 있으므로 사이클을 만들어 제외합니다. 이어 B-D(5)를 넣으면 {A,B,C}와 {D,E}가 합쳐지고, 네 간선의 총비용은 10이 됩니다.

강의자료의 6개 정점 예에서는 1-2(10), 3-6(15), 4-6(20), 2-6(25)를 고른 뒤 1-4(30)는 사이클 때문에 제외하고 3-5(35)를 추가합니다. 선택 간선이 5개로 n-1개가 되었으며 총비용은 10+15+20+25+35=105입니다.

Kruskal 추적법: 비용순 목록을 유지하고, 각 간선마다 두 끝점이 같은 성분인지 확인합니다. ‘비용이 작다’는 조건과 ‘사이클을 만들지 않는다’는 조건을 모두 통과해야 선택됩니다.

Sollin은 여러 트리가 동시에 가장 싼 바깥 간선을 고른다

솔린(Sollin) 알고리즘은 처음에 각 정점을 간선이 없는 하나의 트리로 봅니다. 한 단계가 진행될 때마다 숲의 각 트리가 다른 트리로 나가는 간선 중 최소 비용 간선을 선택하고, 선택된 간선으로 성분들을 합칩니다. Prim이 하나의 트리를 키우고 Kruskal이 간선을 전역 비용순으로 하나씩 검사한다면, Sollin은 여러 트리의 지역 선택을 한 라운드에 모읍니다.

앞의 A~E 그래프 첫 단계에서 A는 A-C(2), B와 C는 B-C(1), D와 E는 D-E(2)를 선택합니다. 같은 간선이 양쪽에서 선택되더라도 한 번만 더하면 숲은 {A,B,C}와 {D,E} 두 트리로 줄어듭니다. 다음 단계에서 두 트리를 잇는 최소 간선 B-D(5)를 선택하면 총비용 10의 하나의 트리가 됩니다.

경계 사례: 한 라운드에서 같은 간선이 두 성분의 최소 간선으로 중복 지목될 수 있습니다. 이는 간선을 두 번 넣는다는 뜻이 아니라, 중복을 제거한 뒤 성분을 합친다는 뜻입니다.

세 알고리즘은 최소 간선을 찾는 범위가 다르다

알고리즘	최소 간선을 찾는 범위	중간 상태	간선 제외 기준
Prim	현재 정점 집합 W와 바깥을 잇는 간선	항상 하나의 연결된 트리	두 끝점이 모두 W 안이어서 확장하지 못함
Kruskal	아직 검사하지 않은 전체 간선	여러 트리로 된 숲 가능	두 끝점이 이미 같은 성분이어서 사이클 생성
Sollin	숲의 각 트리에서 바깥으로 나가는 간선	라운드마다 여러 성분이 동시에 합쳐짐	같은 성분 내부 간선 또는 중복 선택 간선

세 방법은 모두 값이 싼 간선을 택하고 사이클을 피하지만 ‘어디에서 가장 싼가’를 묻는 범위가 다릅니다. 이 범위를 구분하지 않으면 Prim 문제에서 전체 최소 간선을 고르거나, Kruskal 문제에서 현재 트리에 닿은 간선만 찾는 오류가 생깁니다.

풀이에서는 프런티어와 성분을 매 단계 기록한다

1. 목표 확인: 정점 방문 순서인지, 모든 정점을 잇는 최소 비용 간선 집합인지 먼저 구분합니다.
2. 동률 규칙 고정: 인접 정점이나 같은 비용 간선이 여러 개라면 번호순 등 선택 규칙을 정합니다.
3. 탐색 상태 기록: DFS는 스택과 복귀 지점, BFS는 큐와 발견 즉시 표시한 정점을 적습니다.
4. 신장 상태 기록: Prim은 W와 바깥의 경계, Kruskal은 성분 소속, Sollin은 라운드별 숲을 갱신합니다.
5. 간선 선택 검증: 비용만 보지 말고 새 정점 또는 다른 성분을 연결하는지와 사이클 여부를 확인합니다.
6. 완성 검산: 정점 n개가 연결되고 선택 간선이 n-1개이며, 비용 합계에 제외 간선이 들어가지 않았는지 점검합니다.

특히 방문 표시와 간선 선택 표시를 구분해야 합니다. 탐색에서는 정점을 이미 발견했는지가 중복을 막고, 신장 트리에서는 두 끝점의 연결 상태가 사이클을 막습니다. 같은 ‘표시’라도 판정 대상이 다릅니다.

핵심 개념 정리

• DFS: 스택의 최근 갈림길로 복귀하며 한 경로를 깊게 탐색합니다.
• BFS: 큐에 먼저 발견된 정점부터 처리하며 시작점 주변을 층별로 확장합니다.
• 신장 트리: n개 정점을 n-1개 간선으로 사이클 없이 연결합니다.
• Prim: 하나의 연결된 정점 집합과 바깥을 잇는 최소 간선을 선택합니다.
• Kruskal: 전체 간선을 비용순으로 보며 서로 다른 성분을 잇는 간선만 남깁니다.
• Sollin: 숲의 각 트리가 가장 싼 바깥 간선을 골라 라운드 단위로 합쳐집니다.

새 그래프 문제를 만나면 먼저 정점 방문과 간선 연결 중 목표를 고릅니다. 탐색이라면 다음 정점을 보관하는 구조가 스택인지 큐인지 추적하고, 최소 비용 연결이라면 최소 간선을 찾는 범위가 현재 트리의 경계인지, 전체 간선인지, 각 성분의 경계인지 표시합니다. 마지막에는 방문 중복 또는 사이클이 없고 모든 정점이 포함되었는지 검산하면 다섯 알고리즘의 규칙을 섞지 않고 적용할 수 있습니다.

예상문제 10선

1. 그래프 탐색의 결과를 최소 비용 신장 트리 문제와 구분하는 설명으로 가장 적절한 것은?

① 모든 간선의 비용을 오름차순으로 정렬한 목록을 만든다. ② n-1개 간선의 비용 합계만 계산하고 방문 순서는 다루지 않는다. ③ 시작점에서 도달 가능한 정점을 중복 없이 방문하는 순서를 만든다. ④ 각 연결 성분의 최소 비용 간선을 한 라운드에 선택한다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 전체 간선을 비용순으로 보는 것은 Kruskal의 간선 선택 준비이며 정점 방문 순서를 만드는 탐색의 정의가 아니다.
• ② 오답: n-1개 간선과 비용 합계는 신장 트리의 구조와 비용을 검사하는 기준이다.
• ③ 정답: 그래프 탐색은 시작 정점에서 도달할 수 있는 정점을 빠짐없이, 중복 없이 방문하는 연산이다.
• ④ 오답: 각 성분이 바깥의 최소 간선을 고르는 것은 Sollin의 신장 트리 구성 방식이다.

2. 더 방문할 이웃이 없을 때 가장 최근 갈림길로 돌아가는 DFS에 직접 대응하는 자료구조는?

① 스택 ② 큐 ③ 비용순 간선 목록 ④ 연결 성분 집합

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 가장 나중에 들어온 갈림길을 먼저 꺼내는 후입선출 방식이 DFS의 복귀 순서와 같다.
• ② 오답: 먼저 발견한 정점을 먼저 처리하는 큐는 BFS의 층별 확장에 대응한다.
• ③ 오답: 비용순 간선 목록은 Kruskal에서 다음 간선을 고르는 데 쓰이며 DFS의 복귀 지점을 보관하지 않는다.
• ④ 오답: 연결 성분 집합은 사이클 판정에 유용하지만 최근 방문 경로를 복원하는 구조가 아니다.

3. BFS에서 같은 정점이 큐에 여러 번 들어가는 오류를 막는 가장 적절한 시점은?

① 모든 탐색이 끝난 뒤 한꺼번에 방문 표시한다. ② 정점을 큐에서 꺼내고 모든 이웃을 처리한 뒤 표시한다. ③ 같은 정점이 두 번 출력된 것을 확인한 뒤 표시한다. ④ 미방문 정점을 발견해 큐에 넣는 순간 표시한다.

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 탐색 중 방문 정보가 없으면 사이클과 여러 부모를 통해 같은 정점을 계속 발견한다.
• ② 오답: 큐에서 꺼낼 때까지 표시를 늦추면 다른 정점이 그 이웃을 다시 큐에 넣을 수 있다.
• ③ 오답: 중복 출력 후 수정하면 이미 큐와 방문 순서가 손상되므로 예방이 되지 않는다.
• ④ 정답: 발견 즉시 표시하면 이후 다른 정점이 같은 이웃을 보더라도 이미 발견된 정점으로 판정한다.

4. 본문의 A~F 무방향 그래프에서 인접 정점을 알파벳순으로 선택할 때 A에서 시작한 BFS 순서는?

① A-B-D-E-F-C ② A-B-C-D-E-F ③ A-C-F-E-B-D ④ A-B-E-F-C-D

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: B에서 D로 깊게 내려간 뒤 복귀하는 순서로, 본문에서 추적한 DFS 결과다.
• ② 정답: A의 이웃 B와 C를 먼저 큐에 넣고, 그다음 B의 D·E와 C의 F가 발견되어 층별 순서가 된다.
• ③ 오답: 시작 직후 알파벳순에서 B보다 C를 먼저 골라 문제의 선택 규칙과 어긋난다.
• ④ 오답: B의 이웃 D와 E는 같은 단계에서 발견되므로 D를 건너뛰고 E부터 깊게 처리하지 않는다.

5. 정점이 8개인 연결 그래프의 신장 트리가 가져야 할 간선 수는?

① 7개 ② 8개 ③ 9개 ④ 6개

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: n개 정점을 연결하면서 사이클이 없는 트리의 간선 수는 n-1이므로 8-1=7개다.
• ② 오답: 연결된 8정점에 간선이 8개면 트리보다 하나 많아 적어도 하나의 사이클이 생긴다.
• ③ 오답: n+1로 계산하면 사이클 없는 최소 연결 구조의 간선 수를 초과한다.
• ④ 오답: n-2개인 6개로는 8개 정점을 모두 연결할 수 없어 적어도 두 연결 성분이 남는다.

6. 강의자료의 6정점 예에서 선택된 간선 비용이 10, 15, 20, 25, 35일 때 신장 트리의 총비용은?

① 75 ② 90 ③ 105 ④ 135

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 10+15+20+25까지만 더해 정점 5를 연결하는 비용 35를 누락한 값이다.
• ② 오답: 다섯 비용의 합에서 15를 빠뜨린 계산으로 선택 간선 전체를 반영하지 못한다.
• ③ 정답: 10+15+20+25+35=105이며 6정점 신장 트리의 다섯 간선을 모두 더한 값이다.
• ④ 오답: 사이클 때문에 제외된 비용 30의 간선까지 더한 값이므로 실제 트리 비용이 아니다.

7. Prim 알고리즘에서 첫 선택 이후 다음 후보로 비교해야 하는 간선은?

① 아직 검사하지 않은 전체 간선 중 비용이 작은 간선 ② 현재 정점 집합 W와 바깥 정점을 잇는 간선 ③ W 안의 두 정점을 잇는 간선만 ④ 숲의 모든 성분이 각각 고른 간선

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 전체 미검사 간선을 비용순으로 보는 것은 Kruskal의 후보 범위이며 Prim의 연결 영역을 보장하지 않는다.
• ② 정답: Prim은 하나의 트리를 유지하면서 W에 새 정점을 붙이는 경계 간선 중 최소를 고른다.
• ③ 오답: 양 끝점이 모두 W 안이면 새 정점이 추가되지 않고 사이클 가능성만 생긴다.
• ④ 오답: 여러 성분이 각자 최소 바깥 간선을 고르는 방식은 Sollin의 라운드 선택이다.

8. Kruskal 과정에서 비용이 작은 간선의 두 끝점이 이미 같은 트리에 속한다면 어떻게 처리해야 하는가?

① 비용이 작으므로 추가한 뒤 직전에 선택한 간선을 제거한다. ② 일단 보류했다가 마지막에 간선 수가 부족하면 추가한다. ③ 같은 성분 안에서도 두 끝점이 직접 인접하지 않았으면 추가한다. ④ 사이클을 만들므로 그 간선을 제외하고 다음 비용의 간선을 검사한다.

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 강의의 Kruskal 절차는 같은 성분을 잇는 간선을 바로 제외하며 직전 간선을 임의로 교체하지 않는다.
• ② 오답: 두 끝점이 같은 성분이라는 사실은 나중에도 바뀌지 않으므로 마지막에 넣어도 사이클이 생긴다.
• ③ 오답: 직접 간선이 없어도 같은 성분에는 이미 두 끝점을 잇는 경로가 있으므로 새 간선이 사이클을 만든다.
• ④ 정답: 이미 경로가 있는 두 정점을 다시 이으면 사이클이 생기므로 선택하지 않고 비용순 검사를 계속한다.

9. Sollin 알고리즘의 한 라운드를 가장 정확히 설명한 것은?

① 한 시작점의 큐에서 정점을 꺼내며 인접 정점을 방문한다. ② 전체 간선을 하나씩 비용순으로 검사해 같은 성분 간선을 버린다. ③ 숲의 각 트리가 바깥으로 나가는 최소 비용 간선을 고르고 성분들을 합친다. ④ 하나의 W에서 바깥 정점 하나만 선택한 뒤 즉시 다음 라운드를 끝낸다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 큐로 정점을 방문하는 절차는 BFS이며 간선 비용으로 숲을 합치는 과정이 아니다.
• ② 오답: 전체 비용순 목록에서 간선을 하나씩 검사하는 방식은 Kruskal의 핵심 흐름이다.
• ③ 정답: Sollin은 현재 숲의 여러 트리가 각각 최소 바깥 간선을 선택해 한 라운드에서 여러 병합을 진행한다.
• ④ 오답: 하나의 연결 정점 집합 W를 한 정점씩 확장하는 설명은 Prim에 해당한다.

10. 가중치 그래프에서 최소 비용 신장 트리 풀이를 검산하는 순서로 가장 적절한 것은?

① 알고리즘별 후보 범위 확인 → 사이클·성분 판정 → n-1개 간선과 전체 연결 확인 → 선택 비용 합산 ② 전체 간선 비용순 정렬 → 가장 싼 n-1개 선택 → 사이클 확인 생략 → 선택 비용 합산 ③ DFS 방문 순서 확정 → 탐색 간선을 그대로 선택 → 가중치 합산 → 다른 신장 트리 비교 생략 ④ 매번 전체 최소 간선 선택 → 후보 범위 확인 생략 → n-1개에서 종료 → 연결 여부 확인 생략

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 선택 범위를 먼저 지킨 뒤 구조 조건과 비용을 차례로 확인해야 알고리즘 규칙과 신장 트리 조건을 함께 검증할 수 있다.
• ② 오답: 비용이 가장 싼 n-1개라도 같은 성분 안에서 사이클을 만들면 다른 정점이 연결되지 않을 수 있다.
• ③ 오답: DFS가 만든 탐색 신장 트리는 모든 정점을 잇지만 가중치를 기준으로 선택하지 않아 최소 비용을 보장하지 않는다.
• ④ 오답: Prim·Kruskal·Sollin은 최소를 찾는 후보 범위가 다르며, 간선 수만 맞아도 여러 성분으로 끊겨 있을 수 있다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 그래프 탐색과 최소 비용 신장 트리의 상태 변화와 선택 기준을 학습 목적에 맞게 재구성한 비공식 학습자료입니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 자료구조 15강 「그래프 Ⅱ」 강의록(2023)
• 보충 자료: 외부 자료는 사용하지 않았으며 A~F 탐색 예제와 A~E 가중치 예제는 강의 범위 안에서 학습용으로 직접 구성했습니다.
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-08-23