[코딩 테스트]BFS로 보는 [Bool] v.s. [Node], visited 배열 쓸 때와 result 배열만 쓸 때의 차이(서로 관련 있음)

BFS 구현방식이 다양해서 차이를 알아보도록 하자.

 

사전지식

1. DFS, BFS 의 개념

2. DFS, BFS 의 자료구조(인접행렬, 인접리스트)

3. 시간 복잡도

 

목차

1. [Bool] 방식과 [node] 방식의 차이점

2. visited 배열 쓸 때와 result 배열만 쓸 때의 차이점

 

사실 1번 2번은 같은 내용이다.

살펴보자.

 

---

 

1. [Bool] 방식과 [Node] 방식의 차이점

편의상 구분	방식	예시	의미
[Bool] 방식	visited = [False] * N	visited[node] = True	빠른 방문 체크를 위해 사용
[Node] 방식	if node in result:	result.append(node)	방문 여부를 결과 저장을 겸해서 체크

 

---

1️⃣ visited = [False] * N (Bool 리스트)

✅ 장점

• 빠르다! → 시간복잡도 O(1)으로 방문 여부 확인 가능
• 중복 방문 방지가 명확
• 노드 방문 순서와 무관하게 관리 가능

❌ 단점

• result와 visited 두 개의 리스트를 써야 해서 코드가 길어질 수 있음

visited = [False] * len(graph) 
if not visited[node]:
    visited[node] = True 
    result.append(node)

 

---

2️⃣ if node not in result: 방식

✅ 장점

• 코드가 간단해보임
• visited 따로 안 만들어도 됨

❌ 단점

• in 연산은 리스트에서는 O(N) 시간 소요 → 비효율적
• 그래프 크기 커지면 속도 차이 큼
• 실수로 중복 넣기 쉬움

if node not in result: 
    result.append(node)

 

+) 추가 

 

리스트 대신 set()을 쓰면 in 연산이 O(1)이긴 한데, 순서가 유지되지 않아서 탐색 순서를 중요시할 때 문제가 생김.

 

---

2. visited 배열 쓸 때와 result 배열만 쓸 때의 차이

위의 글을 읽으면

visited, result 함께 쓰는 경우 => [Bool] 방식,

result만 쓰는 경우 => [Node] 방식

임을 알 수 있다.

코드로 비교해보자.

 

 

# BFS - visited 사용
from collections import deque

def bfs_with_visited(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
    
    
# BFS - result만 사용
from collections import deque

def bfs_with_result_only(graph, start):
    queue = deque([start])
    result = []

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

 

 

---

결론

상황	추천 방식
노드 수가 적고 간단히 테스트	result만 써도 됨
실전 문제, 탐색 순서 중요, 효율 중시	visited (bool 리스트) 추천
그래프가 커짐 (ex. 수천~수만 노드)	반드시 visited 필요

 

• DFS/BFS에서 visited는 빠르고 명확한 방문 체크 도구
• result만으로 방문 체크하면 단순하지만 비효율적
• 실무/코딩테스트에선 대부분 visited 따로 씀