DFS & BFS

그래프 탐색에서 주로 사용하는 DFS와 BFS에 대해 배워봅니다.

---

DFS

깊이 우선 탐색, 다음 브랜치로 넘어가기 전 해당 브랜치를 모두 탐색하는 것

def dfs(graph, node, visited):
    visited[node] = True
    print(node, end=' ')
    for next_node in graph[node]:
        if not visited[next_node]:
            dfs(graph, next_node, visited)

graph = [
    [],
    [2, 4],
    [5, 7],
    [9, 10],
    [6],
    [2, 8],
    [4, 10, 11],
    [2, 8, 9],
    [5, 7],
    [3, 7],
    [3, 6],
    [6]
]

visited = [False] * 12
dfs(graph, 1, visited)

모든 경로를 방문해야 할 경우 사용함
구현이 간단하지만 검색 속도 자체는 BFS에 비해 느림

DFS 사용 문제

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.

다음 4 x 5 얼음 틀 예시에서는 아이스크림이 3개 생성된다.

구멍이 뚫린 부분은 0, 아닌 부분은 1이다 

00110
00011
11111
00000

정답은 아래와 같으며 3개가 된다

00  0
000

00000  

DFS 사용 문제 코드

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x+1, y) # 하
        dfs(x, y+1) # 우
        return True
    return False
            

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1
print(result)

DFS 복습

자기 자신을 호출하는 순환 알고리즘의 형태이다
노드의 방문 여부를 반드시 검사해야 한다

BFS

너비 우선 탐색, 인접한 노드부터 먼저 탐색하는 것

from collections import deque

def BFS(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()
        print(node, end= ' ')
        for next_node in graph[node]:
            if not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True

graph = [
    [],
    [2, 4],
    [5, 7],
    [9, 10],
    [6],
    [2, 8],
    [4, 10, 11],
    [2, 8, 9],
    [5, 7],
    [3, 7],
    [3, 6],
    [6]
]

visited = [False] * 12
BFS(graph, 1, visited)

최단 경로나 임의의 경로를 찾아야 할 경우 사용함

BFS 사용 문제

N x M 크기의 미로가 있다. 이동할 수 없는 칸은 0, 이동할 수 있는 칸은 1로 표시된다. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하시오

다음 4 x 6 미로에서는 결과가 15가 된다

이동할 수 없는 칸은 0, 이동할 수 있는 칸은 1

101111
101010
101011
111011

정답은 15가 된다

BFS 사용 문제 코드

from collections import deque

def Bfs(graph, n, m):
    Queue = deque([(0,0)])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while Queue:
        x, y = Queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            elif graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                Queue.append((nx, ny))
    return graph[n-1][m-1]

graph = []
n, m = map(int, input().split())
for i in range(n):
    graph.append(list(map(int, input())))
print(Bfs(graph, n, m))

BFS 복습

큐를 사용하여 방문할 노드들을 차례로 꺼내야 한다
노드의 방문 여부를 반드시 검색해야 한다