[2023 알고리즘 스터디] 3조 선병범 4주차 - DFS & BFS 알고리즘

DFS

깊이 우선 탐색 자료라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며 스택 자료구조를 아용한다.

 

DFS의 구체적인 탐색 과정은

 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.

 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면  그 노드를 스택에 넣고 방문

 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.

 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

 

BFS

너비 우선 탐색 자료라고도 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이며 큐 자료 구조를 이용한다.

 

DFS의 구체적인 탐색 과정은

 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.

 2.. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문

 처리합니다.

 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

 

BFS와 DFS의 예시는 다음과 같다

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

from collections import deque

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

graph = [[False] * (n + 1) for _ in range(n + 1)]

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

visited1 = [False] * (n + 1)
visited2 = [False] * (n + 1)

def dfs(v):
    visited1[v] = True
    print(v, end=" ")
    for i in range(1, n + 1):
        if not visited1[i] and graph[v][i]:
            dfs(i)

def bfs(v):
    q = deque([v])
    visited2[v] = True
    while q:
        v = q.popleft()
        print(v , end = " ")
        for i in range(1, n + 1):
            if not visited2[i] and graph[v][i]:
                q.append(i)
                visited2[i] = True


dfs(v)
print()
bfs(v)

 

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

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

N = int(input())
visited = [False]*(N+1)
answer = [False]*(N+1)
tree = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

def bfs(tree,x,visited):
    q = deque([x])
    visited[x] = True
    while q:
        y = q.popleft()
        print(y,'y')
        for i in tree[y]:
            print(i,'i')
            if not visited[i]:
                answer[i] = y
                print(i,answer[i],'answer')
                q.append(i)
                visited[i] = True

bfs(tree,1,visited)

for i in range(2,N+1):
    print(answer[i])

 

https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

 

def dfs(x, y, number):
    if len(number) == 6:
        if number not in result:
            result.append(number)
        return

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    for k in range(4):
        ddx = x + dx[k]
        ddy = y + dy[k]

        if 0 <= ddx < 5 and 0 <= ddy < 5:
            dfs(ddx, ddy, number + matrix[ddx][ddy])


matrix = [list(map(str, input().split())) for _ in range(5)]

result = []
for i in range(5):
    for j in range(5):
        dfs(i, j, matrix[i][j])
print(len(result))

 

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]
def bfs(sx, sy, ax, ay):
    q = deque()
    q.append([sx, sy])
    s[sx][sy] = 1
    while q:
        a, b = q.popleft()
        if a == ax and b == ay:
            print(s[ax][ay] -1)
            return
        for i in range(8):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < n and 0 <= y < n and s[x][y] == 0:
                q.append([x, y])
                s[x][y] = s[a][b] + 1
t = int(input())
for i in range(t):
    n = int(input())
    sx, sy = map(int, input().split())
    ax, ay = map(int, input().split())
    s = [[0] * n for i in range(n)]
    bfs(sx, sy, ax, ay)