[알고리즘] DFS & BFS - 핵심 아이디어

BFS (Breadth-First Search) 너비 우선 탐색

노드 주변을 먼저 탐색하는 방법

• 큐로 구현
• BFS로 탐색하면 항상 최적의 해가 도출된다 (특정 목적지까지 움직인 최단거리를 구할 때 사용)

 

DFS (Depth-First Seach) 깊이 우선 탐색

한 노드로부터 가장 깊게 먼저 탐색하는 방법

• 스택 또는 재귀로 구현
• 간혹 DFS를 사용하면 깊이의 제한이 없어서 무한루프에 빠지는 경우가 종종 있으니 주의

 

알고리즘 특성상 동작 방식이 직관적이지 않다

따라서 IDE 디버깅을 사용하는 것보다 전용 출력 함수를 만들어서 콘솔 창에 print 해보면서 디버깅하는 걸 추천한다

(애초에 코테에서 디버깅 기능을 사용할 수 없다)

 

DFS보다 BFS를 더 선호하는데, 이유는 다음과 같다

• DFS의 무한반복 위험성
• 파이썬의 얕은 최대 재귀 제한
• 재귀 함수 구현의 어려움
• BFS 탐색 후 도출되는 최적해의 원리

 

문제 접근 핵심 아이디어 (BFS 기준)

1. 큐에 어떤걸 담을지 결정한다
2. 메인 로직 : 큐가 빌 때까지 반복하는 메인 로직을 구상한다
3. 탐색 조건 : 해당 노드로 부터 어떤 것들을 탐색하여 큐에 담을지 결정한다 + 방문 기록

방문 기록 방식

• 방문 여부에 따라 True, False로 유지 -> 기본
• 이전 방문 횟수 +1을 기록 -> 최단 방문 횟수를 계산할 때 활용

---

대표 유형

문제에서 탐색할 구조가 어떤 형태로 주어지는지에 따라서 분류

 

인접 리스트

가장 기본적인 유형

인접 리스트는 그래프의 구조를 리스트(배열) 형태로 표현한 방식을 말한다

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

연산을 쉽게 하기 위해, 0번째 노드는 사용하지 않아도 설정해 놓는 게 좋다

 

DFS, BFS어떤 유형을 사용해도 동일한 답을 도출함

(단, 그래프가 깊게 무한히 뻗어나가는 경우에는 DFS를 사용하면 안 됨)

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

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

스택에 넣는 DFS는 BFS의 큐를 스택으로 바꾸기만 하면 된다

 

 

1차원 수직선

현재 위치에서 특정 위치로 이동할 때 걸리는 최단 횟수를 구하는 문제로 출제된다

접근 방식

- 수직선의 MAX값을 찾아서 그 값까지 0으로 초기화된 리스트를 만든다

- 인덱스 == 방문 좌표로, 방문할 때마다 해당 인덱스의 요소 값을 더한다(이게 나중에 최종 움직인 횟수가 된다)

- 큐에 넣을 조건 검사한다 (큐에 넣는다 == 지금 시점으로부터 할 수 있는 경우들을 모두 탐색한다)

리스트를 저런 식으로 만들어서 사용하는 이유는 BFS 특징상, 현재 노드 주변 노드를 모두 검사해야 하는데 이때 방문 횟수가 중복으로 더해지지 않도록 하기 위함이다

 

예시 문제

[응용] 백준 실버 1 숨바꼭질

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

1697번: 숨바꼭질

 

 

2차원 배열

2차원 탐색을 위한 방향벡터를 활용한다

def bfs(x, y):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            # 방향 벡터를 활용
            nx = x + dx[i]
            ny = y + dy[i]
            
		    # 탐색 조건
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if maze[nx][ny] == 0:
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                q.append((nx, ny))

 

방향 벡터 활용 없이 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)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

• 순수 활용
• 연결 요소 세기 (청크 나누기)

방문 기록 리스트 설계

• 2차원 배열을 한 번만 순회 -> 1차원 수직선처럼 설계해도 무방
• 2차원 배열을 여러 번 순회 -> 시간 초과 우려, 따라서 중복을 최소화하게 설계해야 함

 

예시 문제

연결 요소 세기 (청크 나누기)

백준 실버 2 유기농 배추

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

1012번: 유기농 배추

 

순수 활용 (2차원 배열을 한 번만 순회)

백준 실버 1 미로 탐색

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

2178번: 미로 탐색

 

순수 활용 (2차원 배열을 여러 번 순회)

백준 골드 4 아기 상어

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

16236번: 아기 상어