알고리즘 03 - (기본 패턴 02) - (5) 그래프 탐색, BFS (너비 우선 탐색, Breadth-First Search) - “방문한 노드”와 “방문 상태”의 차이점

“방문한 노드”와 “방문 상태”의 차이점

“방문한 노드”와 “방문 상태”는 그래프 탐색 알고리즘(BFS, DFS 등)에서 자주 등장하는 용어로, 연관된 개념이지만 서로 다른 의미를 가집니다.

---

1. “방문한 노드”란 무엇인가?

방문한 노드는 탐색 과정에서 이미 탐색된 특정 노드를 의미합니다.

• 탐색 대상: 그래프의 노드(정점, Vertex).
• 탐색 중 현재 처리된 노드를 “방문한 노드”라고 합니다.
• 노드를 방문했을 때 수행하는 작업:
  1. 데이터를 처리(예: 출력, 기록).
  2. 해당 노드와 연결된 인접 노드들을 탐색 큐/스택에 추가.

예제

방문한 노드: 1
방문한 노드: 2
방문한 노드: 3

여기서 1, 2, 3은 탐색 중 처리된 노드를 의미하며, 이를 “방문한 노드”라고 합니다.

---

2. “방문 상태”란 무엇인가?

방문 상태는 탐색 과정에서 각 노드의 현재 탐색 상태를 추적하는 정보입니다.

• 상태 기록: 특정 노드가 방문되었는지 여부를 나타냅니다.
• 방문 상태의 역할:
  • 중복 탐색 방지: 이미 방문한 노드는 다시 탐색하지 않도록 관리.
  • 탐색 흐름 제어: DFS에서 “현재 탐색 중”인지, “완전히 탐색 완료”되었는지를 기록.
  • 탐색 효율성 향상: 방문 여부를 기록함으로써 불필요한 작업을 줄임.

방문 상태의 표현 방법

• 집합(Set):
  • 방문한 노드를 집합에 추가하여 관리.
  • 예: visited = {1, 2, 3} (1, 2, 3번 노드가 방문됨).
• 리스트(List):
  • 노드의 인덱스를 사용해 방문 여부를 기록.
  • 예: visited = [False, True, True, True] (1~3번 노드가 방문됨).
• 딕셔너리(Dictionary):
  • 노드 값과 방문 여부를 키-값 쌍으로 기록.
  • 예: visited = {1: True, 2: True, 3: True}.

---

3. “방문한 노드”와 “방문 상태”의 차이점

특징	방문한 노드	방문 상태
정의	이미 탐색된 특정 노드.	각 노드의 탐색 여부를 기록한 정보.
목적	탐색 과정 중 현재 처리된 노드를 나타냄.	중복 탐색 방지 및 탐색 흐름 관리.
데이터 구조	특정 노드 값(예: 1, 2, 3).	집합(Set), 리스트(List), 딕셔너리(Dictionary).
역할	탐색 과정에서 처리되는 대상.	탐색 여부 및 진행 상태를 추적.
예시	“방문한 노드: 1”	visited = {1, 2, 3} (1, 2, 3번 노드 방문).

---

4. 예제로 이해하기

그래프 탐색 문제

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

BFS 코드

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문 상태 기록
    queue = deque([start])  # 탐색할 노드

    while queue:
        node = queue.popleft()  # 큐에서 노드 꺼내기

        if node not in visited:  # 방문하지 않은 경우
            visited.add(node)  # 방문 상태 업데이트
            print(f"방문한 노드: {node}")  # 현재 방문한 노드 출력
            queue.extend(graph[node])  # 인접 노드 추가
            print(f"방문 상태: {visited}")  # 방문 상태 출력

출력

방문한 노드: 1
방문 상태: {1}
방문한 노드: 2
방문 상태: {1, 2}
방문한 노드: 3
방문 상태: {1, 2, 3}
방문한 노드: 4
방문 상태: {1, 2, 3, 4}
방문한 노드: 5
방문 상태: {1, 2, 3, 4, 5}

---

5. 요약

• “방문한 노드”:
  • 탐색 과정 중 현재 처리된 노드.
  • 노드의 값(예: 1, 2, 3 등)을 의미.
• “방문 상태”:
  • 탐색 과정에서 각 노드의 탐색 여부를 기록.
  • 중복 탐색 방지 및 효율적인 탐색 관리.

---

6. 암기하기 쉽게 정리

1. 방문한 노드:
   • “현재 탐색 중이거나 탐색이 완료된 대상.”
   • 방문할 때마다 출력되는 값.
2. 방문 상태:
   • “탐색 여부를 추적하는 도구.”
   • 집합(Set)이나 리스트(List)를 사용.

---