DFS, BFS 탐색시 visited 처리

개인생각

DFS, BFS 탐색시 visited 탐색은 굉장히 빈번하게 이루어진다.

visited 를 list 자료구조로 선언하게되면 많은 시간이 낭비될 수 있다.

set 과 같은 탐색에 대한 O(1) 자료구조를 반드시 써야 된다.

---

DFS / BFS 탐색 시 visited 체크에 대한 자료구조 비교

DFS나 BFS로 그래프를 탐색할 때, 이미 방문한 노드인지 체크하는 작업은 필수입니다.
처음엔 주로 list를 이용해 처리하지만, 이 방식에는 성능적인 문제가 존재합니다.

---

❌ list를 사용할 경우

• 중복된 노드가 추가될 수 있음
• 이동할 때마다 모든 요소를 순회하며 체크해야 함
• 탐색 시간 복잡도: O(N)
• 많은 참조와 비교로 인해 속도가 느림

visited = []
if node not in visited:  # O(N) 시간 소요
    visited.append(node)

---

✅ set을 사용할 경우

• 중복 자동 제거
• 노드 방문 여부 체크 시 해시 기반으로 빠르게 탐색
• 탐색 시간 복잡도: O(1)
• 전체 탐색 성능을 크게 향상시킬 수 있음

visited = set()
if node not in visited:  # O(1) 시간 소요
    visited.add(node)

---

🔍 요약

자료구조	중복 방지	탐색 속도	시간 복잡도
list	❌	느림	O(N)
set	✅	빠름	O(1)

---

💡 결론: DFS나 BFS에서 visited는 set으로 관리하는 것이 훨씬 효율적입니다.

---

필요하시면 이 내용을 코드와 함께 블로그 스타일로 더 확장해드릴 수도 있어요!