DFS와 BFS

Posted Dec 23, 2023 Updated Jan 15, 2024

By ParkJinHong 12 min read

DFS와 BFS

그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

DFS(깊이 우선 탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
기본적인 코드는 다음과 같다.

  
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 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] == False:
            dfs(graph, i, visited)

graph는 인접 리스트를 이용한다. 예를 들어, i번 점과 인접한 점은 graph[i]에 해당하는 점들이다. 한 부분을 계속 파고드는 재귀함수의 속성을 이용하여 코드를 구현한다.

BFS(너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘
기본적인 코드는 다음과 같다.

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

def bfs(graph, v, visited):
    q = deque([v])
    visited[v] = True
    while q:
        a = q.popleft()
        print(a, end=' ')
        for i in graph[a]:
            if visited[i] == False:
                q.append(i)
                visited[i] = True

큐를 이용한다는 점이 재미있다. 점 v와 인접한 점들을 queue에 넣어놓고, 다른 가까운 점들부터 처리한다.

백준 - DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

정답 코드

  
import sys
input = sys.stdin.readline
from collections import deque

n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if visited[i] == False:
            dfs(graph, i, visited)

def bfs(graph, v, visited):
    q = deque([v])
    visited[v] = True
    while q:
        a = q.popleft()
        print(a, end=' ')
        for i in graph[a]:
            if visited[i] == False:
                q.append(i)
                visited[i] = True


visited = [False]*(n+1)
dfs(graph, v, visited)
print()
visited = [False]*(n+1)
bfs(graph, v, visited)

위에서 설명한 DFS와 BFS의 기본 코드를 이용하면 풀 수 있는 문제이다.

백준 - 연결 요소의 개수

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력
첫째 줄에 연결 요소의 개수를 출력한다.

정답 코드

  
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            dfs(graph, i, visited)

count = 0
visited = [False]*(n+1)
for i in range(1,n+1):
    if visited[i] == False:
        count += 1
        dfs(graph, i, visited)
print(count)

DFS와 BFS 모두 연결된 점들을 탐색하기 때문에, 둘 중 하나를 구현하고, for문으로 visited[i] = False인 모든 점에 적용해하고 count 해주면 연결 요소의 개수를 구할 수 있다.

백준 - 바이러스

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

정답 코드

  
import sys
input = sys.stdin.readline

def dfs(graph, v, visited):
    global count
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            count += 1
            dfs(graph, i, visited)

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

count = 0
dfs(graph,1,visited)
print(count)

점 v를 1번 컴퓨터로 설정해주고, DFS함수 안에서 if visited[i] == False:(방문)을 통과할 때마다 count += 1를 해주면 간단하게 구할 수 있다.

백준 - 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

정답 코드

  
from collections import deque
import sys
input = sys.stdin.readline

def bfs(v, visited, result):
    visited[v] = 0
    q = deque([v])
    while q:
        a = q.popleft()
        if a == result:
            print(visited[a])
            break
        for i in [a+1,a-1,a*2]:
            if 0 <= i <= 100000 and visited[i] == 0:
                visited[i] = visited[a] + 1
                q.append(i)

n, k = map(int, input().split())
visited = [0]*100001
bfs(n, visited, k)

고민을 정말 많이 했던 문제인데, 이렇게 무식한 방법일 줄은 몰랐다..
수직선의 범위인 0부터 100000까지를 탐색하다가 동생을 발견하면 탐색을 멈추는 방식이다. 가장 빠르게 찾을 수 있는 값을 구하기 때문에 BFS(너비 탐색)를 이용한다. graph로 구성하지 않고,

  
for i in [a+1,a-1,a*2]:
    if 0 <= i <= 100000 and visited[i] == 0:

이렇게 i의 범위를 설정하여 탐색하는 방식이었다.

처음엔 동적 프로그래밍으로 풀어보려고 했는데, 점화식을 구성할 수가 없어서 결국 다른 풀이를 보게되었다.

CS Study, algorithm

Sophomore CodingTest

This post is licensed under CC BY 4.0 by the author.

DFS와 BFS

DFS(깊이 우선 탐색)

BFS(너비 우선 탐색)

백준 - DFS와 BFS

백준 - 연결 요소의 개수

백준 - 바이러스

백준 - 숨바꼭질

Trending Tags