[Algorithm/Python] BFS/DFS 이해하기

💡 DFS(Depth First Search)

: 깊이 우선 탐색 → 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

미로에 갇혔을 때, 가던 길이 막히면 가장 최근에 있었던 갈림길로 되돌아간다 → 스택 연상 가능

** 스택에 지나온 경로를 저장하자 **

• 탐색 시작 노드를 스택에 push → 방문 처리
• 스택이 공백이 아니면 하나의 위치를 꺼냄 → 현재 위치 → 방문 처리
• 꺼낸 현재 위치가 출구 → 탐색 성공 출구가 아니다 → 상하좌우 이웃한 방들을 살펴봄 → 갈 수 있는 모든 방들을 스택에 push → 반복

O(N)의 시간이 소요되고, DFS는 스택을 사용하는 알고리즘 → 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.

 

[구현]

graph = [[], [2, 3, 8], [1, 7, 8], [1, 4, 5], [3, 5], [3, 4], [7], [6, 8], [1, 7]]

visited = [False] * 9

def dfs(Graph, v, Visited):
    Visited[v] = True
    print(v, end=' ')

    for i in Graph[v]:
        if Visited[i] is False:
            dfs(Graph, i, Visited)

dfs(graph, 1, visited)

[활용 예제]

N, M = map(int, input().split())

graph = []

for i in range(N):
    graph.append(list(map(int, input())))

def dfs(x, y):
    if x < 0 or x >= N or y < 0 or y >= M:
        return False

    if graph[x][y] == 0:
        graph[x][y] = 1

        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

result = 0
for i in range(N):
    for j in range(M):
        if dfs(i, j) is True:
            result += 1
print(result)

💡 BFS(Breadth First Search)

: 너비 우선 탐색 → 가까운 노드부터 탐색하는 알고리즘

** 인접한 노드를 반복적으로 큐에 넣어서 탐색 **

• 탐색 시작 노드를 큐에 넣음 → 방문 처리
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 넣음 → 방문 처리
• 위의 과정 반복

O(N)의 시간이 소요되며, 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

[구현]

from collections import deque

graph = [[], [2, 3, 8], [1, 7, 8], [1, 4, 5], [3, 5], [3, 4], [7], [6, 8], [1, 7]]
visited = [False] * 9

def bfs(Graph, s, Visited):
    # 탐색 시작 노드를 큐에 넣음
    queue = deque([s])
    Visited[s] = True  # 방문 처리
    while queue :
        v = queue.popleft()
        print(v, end=' ')

        for i in Graph[v]:
		# 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 넣음
            if Visited[i] is False:
                queue.append(i)
                Visited[i] = True  # 방문 처리

bfs(graph, 1, visited)

[활용 예제]

N, M = map(int, input().split())

graph = []

for i in range(N):
    graph.append(list(map(int, input())))

def dfs(x, y):
    if x < 0 or x >= N or y < 0 or y >= M:
        return False

    if graph[x][y] == 0:
        graph[x][y] = 1
		    
        # 상하좌우를 살피며 방문하지 않은 지점 찾기
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

result = 0
for i in range(N):
    for j in range(M):
        if dfs(i, j) is True:
            result += 1
print(result)