방송대 컴퓨터과학개론 4강: 트리 순회와 그래프 탐색

방송대 컴퓨터과학개론 4강: 트리 순회와 그래프 탐색

자료를 선으로 연결했다고 해서 처리 순서가 저절로 정해지는 것은 아닙니다. 트리는 계층을 만들고, 그래프는 더 자유로운 관계를 표현하며, 순회 규칙은 그 구조를 어떤 순서로 읽을지 결정합니다. 이 글은 노드의 위치를 말하는 용어부터 이진 트리의 높이와 순회, 그래프의 행렬·리스트 표현, 깊이 우선·너비 우선 탐색까지를 ‘모양 → 표현 → 방문 규칙’의 흐름으로 연결합니다.

연결 구조를 읽을 때는 모양·표현·방문 순서를 나눈다

선형 자료구조에서는 앞과 뒤를 따라가면 다음 원소를 비교적 쉽게 정할 수 있습니다. 반면 비선형 자료구조에서는 하나의 원소가 여러 원소와 연결될 수 있으므로, 단순히 “다음으로 간다”는 말만으로는 처리 순서가 충분히 설명되지 않습니다.

이번 강의의 트리와 그래프는 모두 노드와 연결 관계를 다루지만 세 층을 분리해 이해해야 합니다. 첫째, 어떤 노드가 어떤 노드와 연결되어 있는지 구조를 봅니다. 둘째, 그 연결을 행렬이나 리스트와 같은 표현으로 옮깁니다. 셋째, 전위 순회나 깊이 우선 탐색과 같은 방문 규칙을 적용합니다.

판단 층	확인할 질문	대표 개념
모양	연결에 계층과 방향이 있는가	트리, 이진 트리, 무방향·방향 그래프
표현	연결 정보를 어디에 기록하는가	인접 행렬, 인접 리스트
방문 규칙	어느 정점을 먼저 처리하는가	전위·중위·후위 순회, DFS, BFS

판단 핵심: 구조가 같아도 방문 규칙이 다르면 결과 순서가 달라지고, 표현이 달라도 같은 구조를 나타낼 수 있습니다. 시험 문제에서는 먼저 ‘연결 자체’, ‘저장 방식’, ‘처리 순서’ 중 무엇을 묻는지 구분하십시오.

트리는 하나의 루트에서 아래로 뻗는 계층 구조다

트리는 데이터 사이의 계층 관계를 나타내는 비선형 자료구조입니다. 정보를 담는 단위를 노드, 노드 사이를 잇는 선을 간선 또는 가지라고 합니다. 비어 있지 않은 트리에는 가장 위에 있는 루트 노드가 하나만 존재합니다.

한 노드에 연결된 서브트리의 수, 곧 아래쪽으로 뻗는 가지 수를 그 노드의 차수라고 합니다. 차수가 0인 노드는 더 이상 자식이 없는 단말 노드 또는 잎 노드입니다. 강의 도식에서는 루트와 단말 노드를 제외한 중간 노드를 내부 노드 또는 비단말 노드로 구분합니다.

용어	기준	실수하기 쉬운 점
부모·자식	간선 하나로 직접 연결된 위·아래 노드	경로 중간에 다른 노드가 있으면 직접 관계가 아님
형제	부모가 같은 노드	같은 레벨이라는 이유만으로 형제가 되지는 않음
조상	루트에서 해당 노드까지의 경로에 있는 앞선 노드	해당 노드 자신은 제외
후손	해당 노드 아래 경로에 놓인 노드	자식뿐 아니라 더 아래의 노드도 포함
노드의 차수	그 노드가 가진 서브트리 수	전체 트리의 차수와 혼동하지 않기

예를 들어 루트 A의 자식이 B와 C이고, B의 자식이 D와 E라면 A는 D의 조상이고 D는 A의 후손입니다. B와 C는 형제이며 D와 E도 형제이지만, C와 D는 레벨이 다를 뿐 아니라 부모도 다르므로 형제가 아닙니다.

레벨과 높이는 기준점을 먼저 확인해야 계산할 수 있다

레벨은 루트에서 한 노드까지 지나온 간선 수로 셉니다. 강의 기준에서 루트의 레벨은 0이고, 루트의 자식은 레벨 1입니다. 가장 아래 단말 노드의 최대 레벨이 3이라면 트리가 차지하는 레벨 수는 0, 1, 2, 3의 네 단계입니다.

강의는 트리의 깊이 또는 높이를 가장 큰 단말 노드 레벨에 1을 더한 값으로 설명합니다. 따라서 최대 레벨이 3인 예의 높이는 4입니다. 일부 교재는 루트에서 가장 먼 잎까지의 ‘간선 수’를 높이로 정의해 같은 트리를 높이 3이라고 부르기도 합니다. 이 글과 관련 문제에서는 강의의 레벨 수 기준을 따릅니다.

어떤 노드를 새 루트로 보고 그 아래 부분만 떼어 내면 서브트리가 됩니다. 원래 트리에서 루트를 제거하면 서로 분리된 여러 서브트리가 남는데, 이 트리들의 집합을 포리스트라고 합니다.

높이 오답 방지: 그림을 보자마자 숫자를 세지 말고 “루트 레벨이 0인가 1인가”, “높이가 노드 단계 수인가 간선 수인가”를 먼저 확인하십시오. 이번 강의에서는 높이=최대 레벨+1입니다.

이진 트리는 왼쪽과 오른쪽을 구별하는 재귀 구조다

이진 트리는 각 노드가 가질 수 있는 자식이 최대 두 개인 트리입니다. 두 자리는 왼쪽 자식과 오른쪽 자식으로 구별되므로, 자식 하나가 있을 때 그것이 왼쪽인지 오른쪽인지도 구조의 일부입니다. 루트 아래의 왼쪽 부분과 오른쪽 부분 역시 각각 이진 트리라는 재귀적 성질을 가집니다.

노드가 N개일 때 한쪽으로만 이어지는 이진 트리의 높이는 최대 N입니다. 반대로 각 레벨을 위에서부터 빈틈없이 채우면 높이가 가장 작아지며, 강의 기준 최소 높이는 ⌊log₂N⌋+1입니다. 예를 들어 N=8이면 ⌊log₂8⌋+1=4입니다. 높이 3에는 최대 2³-1=7개만 들어가므로 여덟 번째 노드를 담으려면 네 번째 레벨 단계가 필요하다는 방식으로도 검산할 수 있습니다.

이진 트리 종류	모양의 판정 기준	높이 k에서의 특징
포화 이진 트리	모든 레벨이 가득 차고 모든 내부 노드가 두 자식을 가짐	전체 노드 2k-1, 단말 노드 2k-1
완전 이진 트리	마지막 레벨 전까지 가득 차며 마지막은 왼쪽부터 연속 배치	포화 트리의 번호를 앞에서부터 빠짐없이 사용
경사 이진 트리	각 노드의 가지가 한쪽 방향으로만 이어짐	N개 노드의 높이가 N까지 커질 수 있음

완전 이진 트리인지 볼 때는 마지막 레벨의 노드 수만 확인해서는 안 됩니다. 왼쪽 자리가 비었는데 그 오른쪽에 노드가 있으면 중간 번호에 구멍이 생기므로 완전 이진 트리가 아닙니다. 포화는 ‘전부 찼는가’, 완전은 ‘왼쪽부터 끊김 없이 찼는가’로 구별하면 됩니다.

이진 트리 순회는 루트를 언제 처리하느냐로 갈린다

순회는 트리의 모든 노드를 일정한 규칙에 따라 한 번씩 방문하는 과정입니다. 세 기본 순회는 왼쪽 서브트리(L)와 오른쪽 서브트리(R)의 상대적 순서는 유지하고, 루트 데이터(D)를 언제 처리하는지만 바꿉니다.

순회	기호	처리 순서	루트가 출력되는 때
전위 순회	DLR	루트 → 왼쪽 → 오른쪽	두 서브트리보다 먼저
중위 순회	LDR	왼쪽 → 루트 → 오른쪽	왼쪽을 마친 뒤
후위 순회	LRD	왼쪽 → 오른쪽 → 루트	두 서브트리를 마친 뒤

강의 예제의 루트는 A입니다. 왼쪽 서브트리는 B를 중심으로 D, E, G를 포함하고 오른쪽 서브트리는 C를 중심으로 F, H를 포함합니다. 각 순회를 재귀적으로 적용하면 결과는 다음과 같습니다.

• 전위: A → B → D → E → G → C → F → H
• 중위: D → B → G → E → A → F → H → C
• 후위: D → G → E → B → H → F → C → A

전위 순회는 A를 즉시 기록한 뒤 왼쪽 전체를 끝내고 오른쪽으로 갑니다. 중위 순회에서는 루트 A가 두 서브트리 사이에 놓이고, 후위 순회에서는 루트 A가 맨 마지막에 놓입니다. 단순히 그림을 위에서 아래로 읽지 말고 각 노드에서 같은 규칙을 반복해야 합니다.

전위(node): node 처리 → 전위(node.left) → 전위(node.right)
중위(node): 중위(node.left) → node 처리 → 중위(node.right)
후위(node): 후위(node.left) → 후위(node.right) → node 처리

빠른 검산: 전위 결과의 첫 원소와 후위 결과의 마지막 원소는 전체 루트입니다. 중위 결과에서는 루트 왼쪽에 왼쪽 서브트리의 모든 노드가, 오른쪽에 오른쪽 서브트리의 모든 노드가 나타나야 합니다.

그래프는 계층에 묶이지 않은 연결 관계를 표현한다

그래프는 정점의 유한 집합 V와 간선의 유한 집합 E로 이루어지며 G=(V,E)로 씁니다. 트리는 하나의 루트에서 계층을 이루지만, 일반 그래프에는 반드시 루트가 있어야 하는 것도 아니고 모든 연결이 아래쪽으로만 향해야 하는 것도 아닙니다.

무방향 그래프의 간선은 정점의 순서가 중요하지 않은 쌍입니다. 따라서 (1,2)와 (2,1)은 같은 간선입니다. 방향 그래프의 간선은 시작과 도착의 순서가 있는 쌍이며 아크라고도 합니다. 이때 <1,2>는 1에서 2로 가는 연결이므로 <2,1>과 다릅니다.

그래프 용어	뜻	판정 기준
인접	두 정점이 하나의 간선으로 직접 연결됨	중간 정점이 없어야 함
경로	간선으로 연속 연결된 정점의 순서열	경로 길이는 지나온 간선 수
단순 경로	경로에서 정점이 반복되지 않음	같은 정점을 다시 지나지 않음
사이클	시작 정점과 끝 정점이 같은 닫힌 경로	강의 기준 세 정점 이상으로 구성
연결 그래프	모든 정점 쌍 사이에 경로가 존재	직접 간선이 아니라 경로의 존재를 확인

무방향 그래프에서 정점의 차수는 그 정점에 접속한 간선 수입니다. 방향 그래프에서는 들어오는 간선 수를 진입 차수, 나가는 간선 수를 진출 차수라고 나누어 셉니다. 방향을 무시하고 두 수를 한꺼번에 세면 안 됩니다.

트리와 그래프의 관계: 트리는 모든 정점이 연결되어 있으면서 사이클이 없는 특별한 무방향 그래프로 볼 수 있습니다. 정점 사이에 경로가 하나뿐이라는 성질 때문에 하나의 루트를 정하면 부모·자식 계층을 만들 수 있습니다.

인접 행렬은 칸으로, 인접 리스트는 이웃 목록으로 연결을 저장한다

정점이 n개인 그래프를 인접 행렬로 표현하면 n×n 표를 만들고, 정점 v_i에서 v_j로 가는 간선이 있을 때 A[i][j]=1, 없을 때 0을 기록합니다. 무방향 그래프에서는 i와 j의 순서를 바꾸어도 같은 간선이므로 행렬이 주대각선을 기준으로 대칭입니다.

강의 41쪽의 무방향 그래프에는 1-2, 1-4, 2-3, 3-4가 연결되어 있습니다. 이를 행렬로 옮기면 다음과 같습니다.

정점	1	2	3	4	행의 합
1	0	1	0	1	2
2	1	0	1	0	2
3	0	1	0	1	2
4	1	0	1	0	2

대각선이 0인 것은 예제에 자기 자신으로 가는 간선이 없기 때문입니다. 또한 무방향 그래프의 각 행에서 1의 개수를 더하면 해당 정점의 차수와 같으므로, 네 정점의 차수는 모두 2입니다.

인접 리스트는 각 정점별로 직접 연결된 이웃을 나열합니다. 간선이 적은 그래프에서는 0이 많은 큰 표를 만들지 않고 실제 이웃을 중심으로 볼 수 있습니다. 반면 인접 행렬은 두 정점의 교차 칸 하나를 확인하면 연결 여부가 바로 드러납니다.

그림 혼합 주의: 강의 41쪽의 인접 행렬 예와 42쪽의 인접 리스트 예는 서로 다른 그래프입니다. 42쪽 리스트는 1:{2,3,4}, 2:{1,4}, 3:{1,4}, 4:{1,2,3}으로 읽습니다. 두 페이지를 한 그래프의 두 표현이라고 가정해 값을 섞지 마십시오.

깊이 우선과 너비 우선은 다음 후보를 꺼내는 방식이 다르다

그래프 탐색 또는 순회는 한 정점에서 출발해 정점을 체계적으로 방문하는 과정입니다. 이미 방문한 정점을 표시하지 않으면 사이클을 따라 같은 정점을 반복할 수 있으므로, 두 방식 모두 방문 여부를 관리해야 합니다.

깊이 우선 탐색(DFS)은 현재 정점에서 아직 방문하지 않은 인접 정점 하나를 골라 가능한 한 깊게 진행합니다. 더 갈 곳이 없으면 직전 갈림길로 되돌아갑니다. 앞서 배운 자료구조와 연결하면 되돌아갈 경로는 후입선출 방식의 스택 또는 재귀 호출로 관리할 수 있습니다.

너비 우선 탐색(BFS)은 출발점과 가까운 정점부터 층별로 방문합니다. 새로 발견한 정점을 차례대로 대기시키고 먼저 들어온 정점부터 확장하므로 선입선출 방식의 큐와 연결됩니다.

DFS(시작점)
    시작점을 방문 표시하고 스택에 넣는다
    스택이 빌 때까지 아직 방문하지 않은 인접 정점을 따라 깊게 진행한다
    더 갈 곳이 없으면 스택을 따라 되돌아간다

BFS(시작점)
    시작점을 방문 표시하고 큐에 넣는다
    큐가 빌 때까지 맨 앞 정점을 꺼낸다
    그 정점의 미방문 이웃을 방문 표시하고 큐 뒤에 넣는다

구분	DFS	BFS
진행 모양	한 갈래를 끝까지 따라감	출발점에서 가까운 층부터 넓힘
후보 관리	스택·재귀의 후입선출	큐의 선입선출
강의 예의 방문 순서	1→2→4→5→7→6→3	1→2→3→4→5→6→7

방문 순서는 탐색 종류만으로 항상 하나로 고정되는 것은 아닙니다. 한 정점에 미방문 이웃이 여러 개라면 번호가 작은 정점부터 고르는지, 인접 리스트에 먼저 기록된 정점부터 고르는지에 따라 순서가 달라질 수 있습니다. 강의의 결과는 그림에 제시된 이웃 선택 순서를 따른 결과입니다.

과정 핵심: DFS와 BFS 모두 모든 정점을 방문할 수 있지만, ‘다음 후보’를 최근에 발견한 것부터 꺼내면 DFS, 먼저 발견한 것부터 꺼내면 BFS가 됩니다. 문제에 이웃 선택 순서가 주어졌다면 그 순서까지 함께 적용하십시오.

새 연결 문제는 세 단계로 복원한다

1. 구조를 확정합니다. 트리인지 일반 그래프인지, 간선에 방향이 있는지, 왼쪽·오른쪽 순서가 있는지 표시합니다.
2. 표현을 대조합니다. 행렬이라면 행과 열의 정점 순서를, 리스트라면 각 정점의 이웃과 방향을 확인합니다.
3. 방문 규칙을 고정합니다. 이진 트리는 D·L·R의 순서를, 그래프는 DFS·BFS와 이웃 선택 순서를 적습니다.
4. 방문 표시를 갱신합니다. 정점을 처리하거나 후보에 넣는 시점을 일관되게 정해 중복 방문을 막습니다.
5. 불변 조건으로 검산합니다. 순회 결과에 모든 노드가 한 번씩 있는지, 무방향 행렬이 대칭인지, 완전 이진 트리에 중간 빈자리가 없는지 확인합니다.

핵심 개념 정리

• 트리는 하나의 루트에서 계층을 이루며 노드의 차수, 조상·후손, 레벨, 서브트리와 포리스트로 위치 관계를 설명합니다.
• 강의 기준 트리 높이는 최대 레벨+1이고, N개 이진 트리의 최소 높이는 ⌊log₂N⌋+1, 최대 높이는 N입니다.
• 전위·중위·후위 순회는 왼쪽과 오른쪽의 순서는 유지한 채 루트를 처리하는 시점을 바꿉니다.
• 그래프는 G=(V,E)로 나타내며 방향 여부에 따라 간선의 순서, 차수, 경로 해석이 달라집니다.
• 인접 행렬과 인접 리스트는 연결을 저장하는 두 표현이고, DFS와 BFS는 다음 방문 후보를 선택하는 두 규칙입니다.

자료구조 문제의 핵심은 그림을 눈으로 따라가는 것이 아니라 규칙을 먼저 고정하는 데 있습니다. 트리에서는 루트와 좌우 서브트리를, 그래프에서는 정점·간선과 방향을 확인한 뒤, 표현 방식과 방문 규칙을 따로 적용하십시오. 마지막에 노드 누락·중복, 행렬 대칭, 레벨 기준을 검산하면 비슷해 보이는 순회와 탐색 문제를 안정적으로 구분할 수 있습니다.

예상문제 10선

1. 트리에서 차수가 0인 노드를 가리키는 용어는?

① 루트 노드 ② 조상 노드 ③ 형제 노드 ④ 단말 노드

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 루트는 트리의 최상위 노드이며 자식이 있다면 차수가 0이 아닙니다.
• ② 오답: 조상은 루트에서 어떤 노드로 가는 경로의 앞선 노드를 나타내는 관계 용어입니다.
• ③ 오답: 형제는 같은 부모를 가진 노드이며 차수 0 여부와는 별개입니다.
• ④ 정답: 자식 서브트리가 없어 차수가 0인 노드를 단말 노드 또는 잎 노드라고 합니다.

2. 루트 레벨을 0으로 세고 가장 깊은 단말 노드의 레벨이 4일 때, 강의 기준 트리의 높이는?

① 4 ② 5 ③ 8 ④ 16

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 간선 수를 높이로 삼는 다른 정의에는 맞을 수 있지만 강의는 레벨 수를 기준으로 합니다.
• ② 정답: 강의 기준 높이는 최대 단말 노드 레벨+1이므로 4+1=5입니다.
• ③ 오답: 최대 레벨에 2를 곱하는 규칙은 높이 계산과 관련이 없습니다.
• ④ 오답: 2⁴은 특정 레벨의 최대 노드 수와 연결될 수 있으나 높이 자체가 아닙니다.

3. 강의 예제 이진 트리의 전위 순회 결과는?

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

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 전위 DLR은 루트 A를 먼저 처리하고 왼쪽 B 서브트리 전체, 오른쪽 C 서브트리 전체를 순서대로 방문합니다.
• ② 오답: 왼쪽-루트-오른쪽으로 진행한 중위 LDR 결과입니다.
• ③ 오답: 왼쪽-오른쪽-루트로 진행한 후위 LRD 결과입니다.
• ④ 오답: 루트 다음에 오른쪽 서브트리를 먼저 읽어 전위 순회의 L-R 순서를 바꿨습니다.

4. 포화 이진 트리와 완전 이진 트리를 바르게 비교한 것은?

① 포화 이진 트리는 마지막 레벨의 오른쪽부터 노드를 채운다. ② 완전 이진 트리의 모든 내부 노드는 반드시 두 자식을 가진다. ③ 포화는 모든 레벨이 가득 차고, 완전은 마지막 레벨을 왼쪽부터 연속해 채운다. ④ 두 종류 모두 노드가 한쪽 방향으로만 연결된다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 완전 이진 트리의 마지막 레벨은 왼쪽부터 채우며 포화 트리는 빈자리 자체가 없습니다.
• ② 오답: 완전 이진 트리의 마지막 위 레벨에서 오른쪽 자식이 없는 내부 노드가 생길 수 있습니다.
• ③ 정답: 포화는 전 레벨 충족, 완전은 마지막 레벨 이전 충족과 왼쪽 연속 배치가 기준입니다.
• ④ 오답: 한쪽 방향으로만 이어지는 모양은 경사 이진 트리입니다.

5. 강의 기준 높이가 4인 포화 이진 트리의 전체 노드 수는?

① 15 ② 8 ③ 16 ④ 31

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 높이 k인 포화 이진 트리의 노드 수는 2ᵏ-1이므로 2⁴-1=15입니다.
• ② 오답: 2⁴⁻¹=8은 높이 4 포화 이진 트리의 마지막 레벨 단말 노드 수입니다.
• ③ 오답: 2⁴에서 전체 합을 위한 1을 빼지 않았습니다.
• ④ 오답: 31은 높이가 5인 포화 이진 트리의 전체 노드 수입니다.

6. 트리를 특별한 무방향 그래프로 설명한 것은?

① 모든 정점 쌍이 직접 간선으로 연결된 그래프 ② 모든 정점의 차수가 2인 그래프 ③ 시작 정점과 끝 정점이 같은 그래프 ④ 모든 정점이 연결되어 있고 사이클이 없는 그래프

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 모든 정점 쌍의 직접 연결은 완전 그래프의 성질이며 트리는 간접 경로를 허용합니다.
• ② 오답: 트리에는 차수 1인 잎과 다양한 차수의 내부 정점이 존재할 수 있습니다.
• ③ 오답: 시작과 끝이 같은 닫힌 경로는 사이클이며 트리에는 사이클이 없습니다.
• ④ 정답: 무방향 트리는 정점들이 연결되어 있으면서 사이클을 갖지 않는 그래프입니다.

7. 강의 41쪽의 인접 행렬에서 정점 1의 행이 0,1,0,1일 때 정점 1의 차수는?

① 1 ② 2 ③ 3 ④ 4

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 행에 있는 1 하나만 세었으며 정점 2와 정점 4 두 곳의 연결을 모두 반영해야 합니다.
• ② 정답: 무방향 인접 행렬에서 한 행의 1의 개수는 차수이고 1이 두 개입니다.
• ③ 오답: 자기 자신을 나타내는 대각선의 0은 간선이 아니므로 차수에 더하지 않습니다.
• ④ 오답: 행의 칸 수는 정점 수일 뿐 실제 연결 수를 뜻하지 않습니다.

8. 인접 행렬과 인접 리스트에 대한 설명으로 옳은 것은?

① 인접 행렬은 정점별 이웃 이름만 연속해서 적는다. ② 무방향 그래프의 인접 행렬은 반드시 비대칭이다. ③ 행렬은 정점 쌍의 칸에 연결을 표시하고, 리스트는 정점별 이웃을 나열한다. ④ 같은 그래프도 두 표현을 사용하면 간선 수가 달라진다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 정점별 이웃을 나열하는 것은 인접 리스트의 설명입니다.
• ② 오답: 무방향 간선은 양쪽 관계가 같으므로 인접 행렬은 주대각선 기준 대칭입니다.
• ③ 정답: 두 방식은 같은 연결 구조를 각각 n×n 칸과 이웃 목록으로 기록합니다.
• ④ 오답: 표현이 달라도 대상 그래프가 같다면 정점과 간선의 구조는 바뀌지 않습니다.

9. “DFS와 BFS의 방문 순서는 시작점만 같으면 언제나 하나로 고정된다”는 설명의 문제점은?

① DFS와 BFS는 시작 정점을 방문하지 않기 때문이다. ② 그래프 탐색에서는 방문 표시를 사용할 수 없기 때문이다. ③ 미방문 이웃이 여러 개일 때 어떤 이웃을 먼저 고르는지에 따라 순서가 달라질 수 있기 때문이다. ④ BFS는 간선을 사용하지 않고 정점 번호만 정렬하기 때문이다.

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 두 탐색 모두 지정된 시작 정점부터 방문합니다.
• ② 오답: 사이클에서 중복 방문을 막으려면 오히려 방문 표시가 필요합니다.
• ③ 정답: 작은 번호 우선, 리스트 기록 순서 등 이웃 선택 규칙이 달라지면 같은 방식에서도 세부 방문 순서가 바뀝니다.
• ④ 오답: BFS도 그래프의 간선을 따라 이웃을 발견하며 번호 정렬만 수행하는 절차가 아닙니다.

10. 출발 정점에서 간선 수가 가장 적은 층부터 정점을 방문하고 싶을 때 알맞은 선택은?

① 후위 순회와 스택 ② 중위 순회와 재귀 ③ 깊이 우선 탐색과 후입선출 ④ 너비 우선 탐색과 선입선출 큐

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 후위 순회는 이진 트리에서 루트를 나중에 처리하는 규칙이며 거리 층별 그래프 탐색이 아닙니다.
• ② 오답: 중위 순회는 왼쪽-루트-오른쪽 순서로 이진 트리를 읽는 방식입니다.
• ③ 오답: DFS는 한 갈래를 깊게 진행하므로 출발점에서 가까운 층을 먼저 끝낸다는 보장이 없습니다.
• ④ 정답: BFS는 먼저 발견한 정점을 큐에서 먼저 꺼내 확장하므로 출발점에 가까운 층부터 방문합니다.

참고문헌

이 글은 공식 강의자료를 바탕으로 핵심 개념과 풀이 절차를 재구성한 비공식 학습자료입니다.

• 한국방송통신대학교 컴퓨터과학과, 「컴퓨터과학개론 4강 자료구조(2)」 강의록, 2024.
• 한국방송통신대학교, 「대학소개」, https://www.knou.ac.kr/knou/105/subview.do, 검토일 2026-09-06.
• 편집 원칙: 올에이클래스 편집 정책

작성: 올에이클래스 학습연구팀