[코테 스터디] 2주차 : DFS/BFS

그래프 알고리즘

그래프를 표현하고 이해하는 알고리즘
→ 그래프 : 정점(Vertex) 과 간선(Edge)으로 구성된 자료구조 

그래프 구조 예시

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

[분류]

1. 탐색 알고리즘 : 각각의 정점들이 연결된 상태 (DFS, BFS)
   • DFS( Depth First Search ) 
   • BFS( Breadth First Search ) 
   • 그래프의 형태 : 인접 행렬 or 이차원 배열 형태
2. 최단 경로 알고리즘 : 두 정점의 최단 경로 (다익스트라 알고리즘 , 벨만 포드 알고리즘, 플로이드 와샬 알고리즘)
3. 최소 신장 트리 : 모든 정점을 연결하는 최단 경로. 모든 경로를 지나는 최소값 ( 쿠르스칼 알고리즘, 프림 알고리즘) 

DFS (Depth First Search)

DFS는 그래프의 깊이를 우선으로 탐색하는 알고리즘
즉, 한 정점에서 출발하여 가능한 깊이까지 들어가고, 더 이상 갈 곳이 없으면 다시 되돌아오는 방식입니다
DFS는 스택 자료구조를 사용하거나 재귀 호출을 통해 구현

DFS 알고리즘 동작 과정

1. 시작 정점을 스택(또는 재귀 호출)에 추가하고 방문 처리
2. 스택의 최상단 정점을 가져와 인접한 정점 중 방문하지 않은 정점을 스택에 추가하고 방문 처리
3. 더 이상 방문할 정점이 없으면 스택에서 정점을 꺼내고, 다시 스택의 최상단 정점에 대해 2번 과정을 반복
4. 스택이 빈 상태가 되면 탐색을 종료

구현 : 재귀

def dfs_recursive(graph, v, visited):
    visited[v] = True
    print(v, end=' ')  # 방문한 정점 출력

    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited)

# 그래프를 인접 리스트로 표현
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

# 방문 정보를 저장하는 리스트
visited = [False] * len(graph)

# 0번 정점부터 DFS 시작
dfs_recursive(graph, 0, visited)

 

구현 : 스택

def dfs_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        v = stack.pop()
        if not visited[v]:
            print(v, end=' ')  # 방문한 정점 출력
            visited[v] = True
            stack.extend(reversed(graph[v]))  # 인접 정점 추가 (순서를 유지하기 위해 역순으로 추가)

# 0번 정점부터 DFS 시작
dfs_stack(graph, 0)

BFS (Breadth First Search)

BFS는 그래프의 너비를 우선으로 탐색하는 알고리즘
즉, 한 정점에서 출발하여 인접한 모든 정점을 우선 방문하고, 그 다음 깊이로 이동하는 방식
BFS는 큐 자료구조를 사용하여 구현

BFS 알고리즘 동작 과정

1. 시작 정점을 큐에 추가하고 방문 처리
2. 큐의 앞에서 정점을 꺼내 해당 정점에 인접한 모든 정점 중 방문하지 않은 정점을 큐에 추가하고 방문 처리
3. 큐가 빈 상태가 되면 탐색을 종료

구현

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')  # 방문한 정점 출력

        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# 0번 정점부터 BFS 시작
bfs(graph, 0)

요약

• DFS (Depth-First Search):
  • 깊이를 우선으로 탐색
  • 스택 또는 재귀 호출 사용
  • 구현이 간단하고, 그래프의 모든 경로를 탐색할 때 유용
• BFS (Breadth-First Search):
  • 너비를 우선으로 탐색
  • 큐 사용
  • 최단 경로를 찾는 데 유용

 

인접 행렬의 DFS, BFS

인접 행렬은 지도를 그래프 형태로 바꿔놓은 것이라 생각하면 쉬움

'''
6 6
0 1 1 1 1 1
0 1 0 0 0 1
0 1 0 1 0 1
0 1 0 1 0 0 
0 0 0 1 1 0
1 1 1 1 1 0
'''

N, M = map(int, input().split())
arr = []
for _ in range(N):
    row = list(map(int, input().split()))
    arr.append(row)
print(arr)

[0, 1, 1, 1, 1, 1]
[0, 1, 0, 0, 0, 1]
[0, 1, 0, 1, 0, 1]
[0, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0]
[1, 1, 1, 1, 1, 0]

- 6x6 배열이며 (0,0) 에서 (5,5)의 위치로 이동하기

# DFS
visited = [[False] * M for _ in range(N)]
dy = (-1, 1, 0, 0)
dx = (0, 0, -1, 1)
def dfs(y, x):
    print(y, x)
    visited[y][x] = True
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if not(0 <= ny < N and 0 <= nx < M):
            continue
        if arr[ny][nx] == 1:
            continue
        if not visited[ny][nx]:
            dfs(ny, nx)

dfs(0, 0)

# BFS
from collections import deque
def bfs(y, x):
    visited = [[False] * M for _ in range(N)]
    dy = (-1, 1, 0, 0)
    dx = (0, 0, -1, 1)

    visited[y][x] = True
    que = deque()
    que.append((y, x))

    while que:
        y, x = que.popleft()
        print(y, x)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if not(0 <= ny < N and 0 <= nx < M):
                continue
            if arr[ny][nx] == 1:
                continue
            if not visited[ny][nx]:
                visited[ny][nx] = True
                que.append((ny, nx))

bfs(0, 0)

- BFS는 방문 가능다하고 무조건 방문하는 것이 아니라, 방문 가능한 곳을 큐에 넣어두고 순서대로 방문

인접리스트의 DFS, BFS

- 노드(node), 엣지(edge) 개념 활용
- 인접 리스트의 그래프를 인접 행렬로 다시 표현할 수 있지만 그건 메모리 소모가 큼(정점의 개수만큼 배열의 크기가 커지기 때문)
- 따라서 인접 행렬보다 인접 리스트의 형태가 더 효율적일 때가 많음

그래프 구조 예

'''
5 
8
1 2
1 3
1 5
2 3
2 5
3 4
3 5
4 5
'''

N = int(input())
M = int(input())

arr = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    arr[u].append(v)
    arr[v].append(u)


'''
[]
[2, 3, 5]
[1, 3, 5]
[1, 2, 4, 5]
[3, 5]
[1, 2, 3, 4]
'''

# DFS
visited = [False] * (N+1)
def dfs(node):
    print(node)
    visited[node] = True 
    for a in arr[node]:
        if not visited[a]:
            dfs(a)

dfs(1)

# 1 2 3 4 5 순으로 탐색

# BFS
from collections import deque
def bfs(start):
    visited = [False] * (N + 1)
    que = deque()
    que.append(start)
    visited[start] = True 

    while que:
        node = que.popleft()
        print(node)
        for a in arr[node]:
            if not visited[a]:
                que.append(a)
                visited[a] = True

bfs(1)

# 1 2 3 5 4 순으로 탐색