[Python] 알고리즘 개념13 퀴즈 - 그래프와 탐색

 

📌 퀴즈 개요

다음 퀴즈를 통해 그래프(Graph)와 탐색(BFS, DFS) 개념을 정확히 이해하고 있는지 확인해 보세요! 😊

---

 

 

🧩 1. 개념 이해 문제

 

(1) 그래프(Graph)의 특징으로 옳지 않은 것은?

1. 그래프는 노드(Node)와 간선(Edge)으로 이루어진다.
2. 방향 그래프는 모든 간선이 양방향으로 연결되어 있다.
3. 가중치 그래프는 간선에 비용이나 거리가 부여될 수 있다.
4. 그래프는 다양한 자료구조로 표현될 수 있다.

 

(2) 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)에 대한 설명으로 옳지 않은 것은?

1. DFS는 한 방향으로 깊이 탐색하다가 막히면 다시 돌아온다.
2. BFS는 가까운 노드부터 탐색하며, 최단 거리 문제 해결에 유용하다.
3. DFS는 스택(Stack) 또는 재귀(Recursion)로 구현할 수 있다.
4. BFS는 재귀 함수를 이용하여 구현하는 것이 일반적이다.

---

 

 

🧩 2. 실전 문제

 

(3) 다음 그래프에서 BFS 탐색을 수행할 경우 방문 순서는? (시작 노드: 1)

  1
 / \
2   3
|   |
4   5

1. 1 → 2 → 4 → 3 → 5
2. 1 → 3 → 5 → 2 → 4
3. 1 → 2 → 3 → 4 → 5
4. 1 → 3 → 2 → 5 → 4

 

(4) 다음 코드의 실행 결과는?

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set([start])
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {1: [2, 3], 2: [4], 3: [5], 4: [], 5: []}
bfs(graph, 1)

1. 1 2 3 4 5
2. 1 3 5 2 4
3. 1 2 4 3 5
4. 1 3 2 5 4

---

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

(1) 정답: 2
✅ 방향 그래프는 간선이 한쪽 방향으로만 연결될 수도 있습니다.

(2) 정답: 4
✅ BFS는 일반적으로 큐(Queue)를 이용해 구현되며, 재귀로 구현하는 경우는 거의 없습니다.

(3) 정답: 3
✅ BFS는 가까운 노드부터 탐색하며, 1 → 2 → 3 → 4 → 5 순으로 방문합니다.

(4) 정답: 1
✅ BFS 방식으로 탐색하므로 출력은 1 2 3 4 5가 됩니다.

---