BFS/DFS (깊이우선/너비우선) 알고리즘에 대한 정리 - 세기무민

안녕하세요 세기무민입니다.

이번 포스팅에서는 DFS/BFS 알고리즘에 대해 다뤄보도록 하겠습니다.

DFS/BFS?

DFS와 BFS 알고리즘은 코딩테스트에 거이 단골 문제 중 하나입니다. 

DFS는 깊이 우선 탐색 알고리즘

BFS는 너비 우선 탐색 알고리즘

대표적으로 DFS의 경우 재귀함수 또는 스택으로 문제를 해결할 수 있고

BFS의 경우 큐(덱큐)를 이용하여 문제를 해결할 수 있습니다. 

DFS와 BFS를 가장 쉽게 알 수 있는건 아래의 그림으로 볼 수 있습니다. 

[DFS]!

위의 그림처럼 깊이부터 하나씩 탐색하는 방식입니다. 

1에서 가장 가까운 2를 탐색하고 2의 다음 노드인 4를 탐색합니다. 

노드 4 이후로 연결된 노드가 없음으로 노드 1로 다시 이동하여 탐색을 반복해줍니다. 

[BFS!]

BFS는 가장 가 까운 노드부터 탐색하는 방식으로 

노드 1 주변으로 가장 가까운 2를 탐색 후 5를 탐색해줍니다. 

그 후 2와 5노드에서 가장 가까운 순서대로 탐색해주면 됩니다. 

 

예시 알고리즘

[백준_적록색약]

위의 문제는 dfs를 이용하여 풀어주면 되는 문제이며 

이 문제에서 확인해야할 건 녹색과 빨간색을 구분하는 리스트와 녹색과 빨간색을 구분하지 못하는 리스트를 

구분하여서 DFS로 문제를 풀면 됩니다. 

# 적록색약
import sys
sys.setrecursionlimit(10**7)

n = int(input())
arr = []
visitedG = [[False for i in range(n)] for j in range(n)]
visitedN = [[False for i in range(n)] for j in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

count_N = 0
count_G = 0

for i in range(n):
    arr.append(list(input()))
            
def noDfs(strs, x, y):
    visitedN[x][y] = True
    for i in range(4):
        nowX = x + dx[i]
        nowY = y + dy[i]
        if nowX >= 0 and nowX < n and nowY >= 0 and nowY < n:
            if not visitedN[nowX][nowY] and arr[nowX][nowY] == strs:
                noDfs(strs, nowX, nowY)
    
    
def dfs(strs, x, y):
    visitedG[x][y] = True
    for i in range(4):
        nowX = x + dx[i]
        nowY = y + dy[i]
        if nowX >= 0 and nowX < n and nowY >= 0 and nowY < n:
            if visitedG[nowX][nowY] == False:
                if strs == 'R' or strs == 'G':
                    if arr[nowX][nowY] == 'G'or arr[nowX][nowY] == 'R':
                        dfs(strs, nowX, nowY)
                else:
                    if arr[nowX][nowY] == strs:
                        dfs(strs, nowX, nowY)
            


for i in range(n):
    for j in range(n):
        if not visitedN[i][j]:
            count_N += 1
            noDfs(arr[i][j], i, j)
        if not visitedG[i][j]: 
            count_G += 1
            dfs(arr[i][j], i, j)

print(count_N, count_G)

[백준_연구소]

이 문제는 브루트포스와 BFS를 혼합한 문제 중 하나이다. 

가장 중요한 포인트는 벽을 3번 쳤을 때 미감염 구역의 최대값을 구해주면 되는 문제이다. 

사실 BFS로 탐색하면서 벽을 하나씩 쳐보면 되지만..(브루트포스)

이렇게 접근하면 문제의 시간초과로 풀 수 없다. 

따라서 바이러스가 없는 구역을 기준으로 조합을 이용하여 벽을 하나씩 쳐주고 

바이러스를 퍼트려서 가장 최대의 감염되지 않은 구역을 찾으면 됩니다. 

import copy
import sys
from collections import deque
from itertools import combinations


dx = [0, 0, 1, -1]
dy = [1, -1, -0, 0]

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
result = 0

virus = 2
empty = 0
wall = 1

virus_graphs = []
noVirus_graphs = []

for i in range(n):
    for j in range(m):
        if graph[i][j] == virus:
            virus_graphs.append((i, j))
        elif graph[i][j] == empty:
            noVirus_graphs.append((i, j))


def bfs(x, y):
    queue = deque()
    queue.append([x,y])
    while queue:
        a, b = queue.popleft()
    
        for i in range(4):
            now_x = a + dx[i]
            now_y = b + dy[i]
            if 0 <= now_x < n and 0 <= now_y < m:
                if empty_graph[now_x][now_y] == empty:
                    empty_graph[now_x][now_y] = virus
                    queue.append([now_x, now_y])

    return empty_graph

answer = 0
for i in combinations(noVirus_graphs, 3):
    empty_graph = copy.deepcopy(graph)
    for x, y in i:
        empty_graph[x][y] = wall
    
    for x, y in virus_graphs:
        empty_graph = bfs(x, y)
        
    count = 0
    
    for i in empty_graph:
        count += i.count(0)
    
    result = max(result, count)

print(result)

 

백준 문제

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

14502번: 연구소

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

10026번: 적록색약