[코딩 테스트]Python을 이용한 BFS, DFS 구현 방법(반복문, 재귀)(인접행렬, 인접 리스트)

 

 

 

 

BFS, DFS 구현할 때 헷갈리던 부분 총정리!

갑니다~

---

사전지식

1. 알고리즘 BFS, DFS 개념

2. 자료구조 스택, 큐 개념

3. 알고리즘 재귀 개념

 

중요 차이점

BFS - 1. 반복문만(큐)

DFS - 1. 반복문(스택) 2. 재귀함수

 

입력 자료구조

1. 인접행렬

2. 인접리스트(코딩 테스트에서 많이 씀)

 

목차

0. 입력 예시

1. BFS 구현

2. DFS 구현

3. 인접행렬보다 인접리스트를 많이 쓰는 이유

4. 결론

 

---

입력예시

# 그래프 예시. 간단한 무방향 그래프

     0
    / \
   1   2
    \ /
     3
     
# 간선 목록
(0, 1), (0, 2), (1, 3), (2, 3)

 

입력 자료구조

# 인접 행렬
adj_matrix = [
    [0, 1, 1, 0],  # 0번 노드는 1, 2와 연결
    [1, 0, 0, 1],  # 1번 노드는 0, 3과 연결
    [1, 0, 0, 1],  # 2번 노드는 0, 3과 연결
    [0, 1, 1, 0]   # 3번 노드는 1, 2와 연결
]


# 인접 리스트
adj_list = [
    [1, 2],    # 0번 노드와 연결된 노드
    [0, 3],    # 1번 노드
    [0, 3],    # 2번 노드
    [1, 2]     # 3번 노드
]

 

BFS 구현

# 인접 행렬 + 큐 자료구조(반복문)
from collections import deque

def bfs_adj_matrix_queue(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])
    result = []

    visited[start] = True

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in range(len(graph)):
            if graph[node][neighbor] and not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    return result


# 인접 리스트 + 큐 자료구조(반복문)
from collections import deque

def bfs_adj_list_queue(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])
    result = []

    visited[start] = True

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    return result

 

 

DFS 구현

# 1. 인접행렬
# 1-1. 인접 행렬 + 스택 자료구조(반복문)
def dfs_adj_matrix_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]
    result = []

    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            result.append(node)
            for neighbor in range(len(graph) - 1, -1, -1):
                if graph[node][neighbor] and not visited[neighbor]:
                    stack.append(neighbor)
    return result


# 1-2. 인접 행렬 + 재귀
def dfs_adj_matrix_recursive(graph, start, visited=None, result=None):
    if visited is None:
        visited = [False] * len(graph)
    if result is None:
        result = []

    visited[start] = True
    result.append(start)

    for neighbor in range(len(graph)):
        if graph[start][neighbor] and not visited[neighbor]:
            dfs_adj_matrix_recursive(graph, neighbor, visited, result)
    return result


# 2. 인접 리스트
# 2-1. 인접 리스트 + 스택 자료구조(반복문)
def dfs_adj_list_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]
    result = []

    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            result.append(node)
            for neighbor in reversed(graph[node]):
                if not visited[neighbor]:
                    stack.append(neighbor)
    return result
    
    
# 2-2. 인접 리스트 + 재귀
def dfs_adj_list_recursive(graph, start, visited=None, result=None):
    if visited is None:
        visited = [False] * len(graph)
    if result is None:
        result = []

    visited[start] = True
    result.append(start)

    for neighbor in graph[start]:
        if not visited[neighbor]:
            dfs_adj_list_recursive(graph, neighbor, visited, result)
    return result

 

 

인접행렬보다 인접리스트를 많이 쓰는 이유

이유는 단순히 "간단해서"가 아니라, 성능 + 편리함 + 확장성이 좋아서 그렇다.

---

✅ 왜 인접리스트가 코테에서 더 자주 쓰일까?

1️⃣ 메모리 효율 (특히 희소 그래프에서 유리함)

• 인접행렬은 항상 NxN 크기의 2차원 배열 사용 → 메모리 낭비 많음
• 인접리스트는 연결된 노드만 저장 → 간선 적으면 아주 효율적

---

2️⃣ 연결 정보 탐색이 더 직관적

# 인접행렬 
for neighbor in range(len(graph)): 
	if graph[node][neighbor]: 
    	...

# 인접리스트 
for neighbor in graph[node]: 
	...

→ 인접리스트가 바로 연결된 애들만 돌아서 빠르고 간단

---

3️⃣ 가중치 그래프도 처리하기 쉬움

• 인접리스트는 가중치를 이렇게 표현:

graph = [ 
	[(1, 4), (2, 2)], # 0번 노드 → 1까지 비용 4, 2까지 비용 2 
	... 
]

 

→ 다익스트라, 벨만포드 등에서 바로 사용 가능
→ 인접행렬은 가중치까지 넣으면 복잡하고 무겁고 느려짐

---

4️⃣ 코테에서는 입력이 간선 리스트로 주어짐

예: N M u1 v1 u2 v2 ...

 

• 이걸 인접리스트로 바꾸는 게 더 직관적:

graph = [[] for _ in range(N)] 

for u, v in edges: 
    graph[u].append(v) 
    graph[v].append(u) # 무방향 그래프일 경우

 

---

❗ 예외는?

• 노드 수가 작고, 연결 여부 체크가 자주 필요한 문제
  → 인접행렬이 더 편한 경우도 있음

예:

• "i번 노드와 j번 노드가 연결되어 있는가?" 를 자주 물을 때
• 플로이드-워셜처럼 모든 정점 간 거리 다뤄야 할 때

 

---

결론

비교 항목	인접리스트	인접행렬
✅ 메모리 효율	👍	👎
✅ 구현 편의성	👍	중간
✅ 가중치 표현	👍	복잡함
✅ 대규모 그래프	👍	👎
✅ 연결 여부 확인	👎 (O(N))	👍 (O(1))

 

 

코테 기본 세팅은 대부분 인접리스트로 간다!