5. 그래프 탐색- DFS,BFS

문제:  그래프에서  깊이  우선  탐색(Depth-First  Search,  DFS)과  너비  우선  탐색 (Breadth-First Search, BFS)의 개념과 예시를 들어주세요.

DFS는 가능한 하나의 길을 깊이로 끝까지 탐색하고, 그 후에 필요시(막히면)이전 단계로 돌아가는 방법입니다.

 

BFS는 시작 노드에서 가까운 노드부터 순서대로 탐색하는 방법입니다.

 

DFS는 스택을 사용하고 BFS는 큐를 사용합니다.

DFS는 경로를 빠르게 탐색에 유리하지만 찾은 경로가 시작노드와의 거리가 최단거리는 알수없으나,

BFS는 찾은경로가 최단 경로임을 보장할수 있습니다.

관련 개념:

Depth-First Search (깊이 우선 탐색): 깊이 방향으로 경로를 탐색하는 데 적합한 그래프 탐색 알고리즘입니 다.
Breadth-First Search (너비 우선 탐색): 너비 방향으로 최단거리를 탐색하는 그래프 탐색 알고리즘입 니다.
Stack (스택): DFS에서 사용되는 LIFO(Last In, First Out) 구조로 나중들어온것이 처음나오는 자료구조입니다.
Queue (큐): BFS에서 사용되는 FIFO(First In, First Out) 구조로 처음들어온것이 처음나오는 자료구조입니다.

 

 

그래프 탐색 알고리즘 중 **깊이 우선 탐색(DFS: Depth-First Search)**와 **너비 우선 탐색(BFS: Breadth-First Search)**은 그래프나 트리의 모든 노드를 방문하기 위한 대표적인 알고리즘입니다. 두 알고리즘은 서로 다른 방식으로 노드를 방문하며, 특정 상황에 따라 적합한 탐색 방법이 달라집니다. 각 알고리즘의 특징과 동작 방식을 설명하겠습니다.

### 1. 깊이 우선 탐색 (DFS: Depth-First Search)

#### 개념
DFS는 그래프에서 **최대한 깊이**로 탐색한 후, 더 이상 갈 곳이 없으면 **다시 되돌아오는(backtracking)** 방식으로 동작합니다. 즉, 한 노드에서 출발하여 다음 노드를 탐색할 때, 더 깊이 들어갈 수 있을 때까지 계속 탐색하다가 막히면 직전 노드로 돌아가 다른 경로를 탐색합니다.

#### 동작 방식
1. 시작 노드를 스택에 넣습니다.
2. 스택에서 노드를 꺼내 해당 노드를 방문하고, 아직 방문하지 않은 인접한 노드를 스택에 넣습니다.
3. 이 과정을 반복하며 더 이상 방문할 노드가 없을 때까지 탐색합니다.

#### 주요 특징
- **스택(Stack)** 또는 **재귀(Recursion)**를 이용해 구현할 수 있습니다.
- DFS는 **깊은 경로**를 우선 탐색하므로, 주로 **경로 탐색**에 유용합니다.
- **재귀 호출**을 통해 간단하게 구현할 수 있지만, 재귀 깊이에 따라 스택 오버플로우 위험이 있습니다.

#### 시간 복잡도
- 그래프의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(V + E)입니다. 여기서 V는 노드(정점)의 개수, E는 간선의 개수를 의미합니다.

#### DFS의 활용 예시
- **미로 탐색**: 한 경로를 끝까지 탐색한 후, 막히면 다른 경로로 이동하는 방식.
- **사이클 검출**: 그래프에 사이클이 존재하는지 여부를 탐색할 때 유용.
  

def dfs(graph, start, visited=set()):
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

 

### 2. 너비 우선 탐색 (BFS: Breadth-First Search)

#### 개념
BFS는 **가장 가까운 노드**부터 차례대로 탐색하는 방식입니다. 즉, 탐색을 할 때 현재 노드와 **인접한 모든 노드를 먼저 탐색**한 후, 그 다음으로 인접한 노드들의 이웃을 탐색합니다. 한 단계씩 탐색 영역을 넓혀가는 방식이라고 할 수 있습니다.

#### 동작 방식
1. 시작 노드를 큐에 넣습니다.
2. 큐에서 노드를 꺼내 방문하고, 인접한 노드들을 모두 큐에 넣습니다.
3. 큐가 빌 때까지 이 과정을 반복하며 탐색을 진행합니다.

#### 주요 특징
- **큐(Queue)**를 사용하여 구현합니다.
- BFS는 **가장 가까운 경로**를 우선 탐색하므로, **최단 경로 탐색**에 유용합니다.
- 재귀 호출 없이 **반복문**을 통해 구현됩니다.

#### 시간 복잡도
- BFS 역시 그래프의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(V + E)입니다.

#### BFS의 활용 예시
- **최단 경로 탐색**: 가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 찾을 때.
- **사회적 네트워크 분석**: 연결된 관계망에서 거리가 가까운 친구나 지인들을 먼저 탐색하는 방식.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

 

DFS는 주로 **탐색의 경로**가 중요한 경우에 사용되고, BFS는 **최단 경로 탐색**과 같이 **가장 가까운 노드**를 우선으로 탐색하는 경우에 적합합니다.

 

------------------------------------------------------------------------------------------

 

https://youtu.be/y3zZDFNt-Zk

 

 

------------------

14. 문제: 그래프에서 사이클 탐지(Cycle Detection) 방법 중 깊이 우선 탐색(DFS) 기반 방법에 대해 설명해 주세요. 
답변:
DFS를 사용한 사이클 탐지 방법은 각 노드를 방문하면서 노드의 상태를 기록합니다. 방 문 중에 이미 방문한 노드가 현재 탐색 경로에 있으면 사이클이 존재한다고 판단합니다. 주로 그래프를 재귀적으로 탐색하며 사이클을 찾습니다.
관련 개념:
DFS (깊이 우선 탐색): 그래프의 노드를 깊이 방향으로 탐색하는 방법입니다. Back Edge (백 엣지): DFS 탐색 중 현재 경로에 있는 노드로 가는 간선입니다.