알고리즘 03 - (자료구조 03) Que - “방문 상태”란 무엇인가?

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

방문 상태는 그래프 탐색에서 특정 노드가 탐색 중인지, 이미 탐색되었는지, 혹은 아직 탐색되지 않았는지를 나타내는 정보입니다.

“방문 상태”의 역할

1. 중복 탐색 방지:
   • 이미 탐색된 노드(방문 상태로 기록된 노드)는 다시 탐색하지 않음.
   • 이는 무한 루프 방지와 탐색 효율성 향상에 필수적입니다.
2. 탐색 흐름 추적:
   • BFS/DFS 탐색 과정에서 어떤 노드가 탐색되었는지 기록하여 탐색 순서를 확인.
3. 탐색 완료 여부 확인:
   • 탐색이 끝난 후, 방문한 노드들의 상태를 이용해 탐색 결과를 평가.

---

방문 상태의 표현 방식

1. 집합(Set)

• 방문한 노드를 집합에 저장합니다.
• 파이썬 코드에서 visited = set()로 관리.

visited.add(node)  # 노드를 방문 상태로 기록
if node in visited:  # 이미 방문한 경우
    pass

2. 리스트(List)

• 노드의 인덱스를 기준으로 방문 여부를 기록.
• 방문: True, 미방문: False.

visited = [False] * num_nodes
visited[node] = True  # 노드를 방문 상태로 설정

3. 딕셔너리(Dictionary)

• 그래프가 딕셔너리 형태일 경우, 각 노드의 방문 상태를 key-value로 저장.

visited = {}
visited[node] = True  # 노드를 방문 상태로 설정

---

방문 상태의 예제

BFS 탐색에서 방문 상태의 사용

코드에서 visited 집합이 방문 상태를 관리하는 역할을 합니다.

1. 방문 여부 확인:

   if node not in visited:  # 노드가 방문되지 않았으면
   

2. 방문 상태 업데이트:

   visited.add(node)  # 현재 노드를 방문 상태로 설정
   

3. 인접 노드 처리:

   next_nodes = [n for n in graph[node] if n not in visited]
   queue.extend(next_nodes)  # 방문하지 않은 노드만 큐에 추가
   

---

방문 상태와 탐색 과정

1. 초기 상태:
   • 방문 상태: 빈 집합 {}.
   • 큐에 시작 노드 추가: [1].
2. 탐색 과정:
   • 노드를 큐에서 꺼냄.
   • 방문 상태에 추가.
   • 인접 노드 중 방문하지 않은 노드를 큐에 추가.
3. 종료 조건:
   • 큐가 비면 탐색 종료.

---

“방문 상태”가 정렬을 의미하지 않는 이유

• 방문 상태는 탐색된 노드가 기록된 순서일 뿐, 값을 정렬하는 작업과는 다릅니다.
• BFS 탐색에서는 노드가 큐에 추가된 순서로 방문 상태가 기록되지만, 이 순서는 노드 값의 정렬과는 무관합니다.

예:

입력 그래프:

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

방문 상태:

• 탐색 순서에 따라 {1, 2, 3, 4, 5}가 기록됩니다.
• 그러나 이 순서는 단순히 탐색 흐름에 따른 결과로, 정렬 작업과는 관련이 없습니다.

---

정리

• 문제 제목: BFS(너비 우선 탐색)를 이용한 그래프 탐색 및 방문 상태 추적.
• 방문 상태란?
  • 특정 노드가 탐색되었는지 여부를 기록하는 정보.
  • 중복 탐색 방지, 탐색 흐름 관리, 탐색 완료 여부 확인에 사용.
• 방문 상태의 표현:
  • 집합(Set), 리스트(List), 딕셔너리(Dictionary) 등으로 관리.
• 방문 상태와 정렬은 다름:
  • 방문 상태는 탐색된 노드의 기록이고, 정렬은 값을 재배열하는 작업.