BFS

1. BFS란?

BFS는 말 그대로 "너비를 우선으로 탐색"하는 알고리즘이야.\
즉, 현재 정점에서 가까운 정점부터 차례로 탐색해 나가는 방식이야.

---

2. BFS의 핵심 원리

BFS는 큐(Queue) 자료구조를 활용해서 동작해.

탐색 흐름 요약:

1. 시작 노드를 큐에 넣고 방문 처리한다.
2. 큐에서 노드를 꺼내고
3. 그 노드에 인접한 정점들 중에서 아직 방문하지 않은 정점을 큐에 넣는다.
4. 큐가 빌 때까지 2~3을 반복한다.

---

3. 예시를 들어보자

그래프:

1
| \
2  3
   |
   4

BFS의 탐색 순서:

1 → 2 → 3 → 4

큐의 변화 과정:

• 시작 노드: 1
• 큐 상태: [1]
• 방문 순서: 1
• → 인접한 노드 2, 3을 큐에 추가 → 큐 상태: [2, 3]
• 다음 방문: 2 → 큐 상태: [3]
• 2의 인접 노드 없음 → 다음 방문: 3 → 인접한 노드 4 추가 → 큐 상태: [4]
• 다음 방문: 4 → 큐 상태: []
• 종료

---

4. BFS에 필요한 구성 요소

• 그래프: 인접 리스트로 표현
• 방문 여부 리스트: 중복 방문 방지
• 큐: 탐색 순서를 유지하기 위해 사용

---

5. BFS의 특징

항목	설명
탐색 순서	가까운 정점부터 탐색
사용 자료구조	큐 (FIFO)
재귀?	❌ (반복문 기반으로 구현)
경로 찾기 문제	최단 거리 탐색에서 유용
시간 복잡도	O(V + E) (V: 정점, E: 간선)

---

6. BFS vs DFS 비교

기준	BFS	DFS
탐색 순서	가까운 노드부터	깊이 있는 노드부터
자료구조	큐 (Queue)	스택 (Stack) or 재귀
구현 방식	반복문 기반	보통 재귀 기반
사용 예시	최단 거리, 네트워크 탐색	백트래킹, 미로 찾기 등

---

컴퓨터적 사고 흐름

• "지금 내 주변(현재 정점의 인접 정점)을 먼저 보고,\
  그다음 인접한 정점들의 주변을 보는 식으로 확장해나가자."

DFS는 깊이 파고들지만,\
BFS는 층층이 탐색한다는 점이 핵심이야.

사이클 탐색하기

예시 그래프가 있다고 해보자:

1 — 2
|   |
4 — 3

여기서 1번 노드부터 BFS를 시작한다고 하자.

---

BFS 흐름 (중요한 부분 표시할게)

1. 시작: 1

   • 방문 표시: visited[1] = True
   • 큐: [1]

2. 1을 꺼내고, 이웃 2와 4를 방문

   • parent[2] = 1, parent[4] = 1
   • 방문 표시: visited[2] = True, visited[4] = True
   • 큐: [2, 4]

3. 이제 2를 꺼냄 → 이웃은 1(이미 방문), 3

   • 3은 미방문이니까 방문함 → parent[3] = 2
   • 큐: [4, 3]

4. 이제 4를 꺼냄 → 이웃은 1(부모), 3

→ 여기서 중요한 상황이 등장해!

---

문제 상황: 4 → 3으로 가는 간선을 탐색할 때

• 3은 이미 방문했어
• 그런데 3은 4의 부모가 아니야 (parent[4]는 1이니까)

즉, 4에서 3으로 가는 간선은 다른 경로로 이미 방문된 노드로 가는 길이야. 예를 들면 다음과 같은 경로를 생각할 수 있어:

1 → 2 → 3
↓         ↑
4 --------

이처럼 3을 두 번 만나게 되는 경우가 발생했는데, 이때 두 번째로 만났을 때의 이전 노드(4)가 3의 부모가 아니라는 점이 중요해.
→ 이건 사이클이 존재한다는 증거야.

---

그래서 요약하면

• 무방향 그래프에선 자기 부모(즉, 자기를 호출한 이전 노드)는 다시 돌아가도 괜찮아.
• 그런데 부모가 아닌데 이미 방문한 노드를 다시 만나면?
  • 그건 다른 경로로 이미 방문한 노드다 → 사이클이다!

---

핵심 조건 다시 말하면:

if visited[u] and parent[pop_data] != u:
    # 이미 방문한 노드를 만났고,
    # 그 노드가 부모 노드가 아니라면 → 사이클 발생!

• visited[u]: 이미 방문한 노드다.
• parent[pop_data] != u: 이 노드는 현재 노드의 부모가 아니다.
• 즉, 다른 경로로 다시 이 노드에 도달했다는 의미야 → 사이클이 있다는 뜻!

---