BFS (너비 우선 탐색, Breadth-First Search)와 DFS (깊이 우선 탐색, Depth-First Search)

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

BFS는 그래프에서 가까운 노드부터 탐색하는 방식입니다. 주로 큐(Queue) 자료구조를 사용하여 구현합니다.

특징

• 최단 경로 탐색에 유리함 (가중치가 동일한 그래프에서 최단 경로 찾을 때 사용)
• FIFO (First-In-First-Out) 구조의 큐를 활용
• 노드를 방문하면 큐에 삽입하고, 큐에서 꺼내면서 인접 노드를 방문

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

DFS는 그래프에서 한 방향으로 갈 수 있을 때까지 탐색한 후, 더 이상 진행할 수 없으면 되돌아가는 방식입니다. 주로 스택(Stack) 혹은 재귀(Recursion) 를 이용합니다.

특징

• 백트래킹(Backtracking) 문제에서 많이 사용됨
• 스택 (Stack) 혹은 재귀를 활용하여 구현
• 모든 노드를 한 번씩 방문할 때 적절한 방법

큐 (Queue) & 스택 (Stack) 자료구조

큐(Queue)와 스택(Stack)은 선형 자료구조로, 데이터를 추가하고 삭제하는 방식이 다르다. 각각 FIFO(First In First Out) 와 LIFO(Last In First Out) 의 특징을 갖는다.

큐 (Queue)

먼저 들어온 데이터가 먼저 나가는 구조 (FIFO: First In, First Out)

특징

• 선입선출(FIFO) 방식: 먼저 들어온 데이터가 먼저 나감.
• enqueue(): 데이터를 큐에 추가
• dequeue(): 큐에서 데이터를 제거 (가장 먼저 들어온 데이터가 제거됨)
• 주로 BFS(너비 우선 탐색), 캐시(Cache) 구현, 프로세스 스케줄링 등에 사용됨.

# collections.deque는 양방향 큐(Double-ended Queue) 를 제공하는 자료구조
from collections import deque

# 큐 생성
queue = deque()

# 데이터 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

print(queue)  # deque([1, 2, 3])

# 데이터 제거 (dequeue)
queue.popleft()  # 1 제거
print(queue)  # deque([2, 3])

삽입(Enqueue)하고 싶을 때에는 append로 한다.(오른쪽에 삽입)
A - B - C - D --> A - B - C - D - E
제거(Dequeue)하고 싶을 때에는 popleft로 한다.(왼쪽 끝 요소 제거 후 반환)
A - B - C - D --> B - C - D

큐 자료구조는 O(1)의 시간 복잡도로 앞에서 제거, 뒤에서 추가 한다.
리스트의 pop(0)은 시간 복잡도 O(n) 시간이 걸린다.
list.insert(0, x) -> O(n)

스택 (Stack)

마지막에 들어온 데이터가 먼저 나가는 구조 (LIFO: Last In, First Out)

특징

• 후입선출(LIFO) 방식: 마지막에 들어온 데이터가 먼저 나감.
• push(): 데이터를 스택에 추가
• pop(): 스택에서 데이터를 제거 (가장 최근에 추가된 데이터가 제거됨)
• 주로 DFS(깊이 우선 탐색), 백트래킹(Backtracking), 괄호 검사(Valid Parentheses) 등에 사용됨.

# 스택 생성
stack = []

# 데이터 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)

print(stack)  # [1, 2, 3]

# 데이터 제거 (pop)
stack.pop()  # 3 제거
print(stack)  # [1, 2]

리스트의 append()와 pop()은 O(1)이므로 빠르게 동작한다.

DFS로 풀지 BFS로 풀지 판단 기준

• 모든 경로를 탐색해야할 때, 경로 자체보다는 가능한 경우의 수를 구할 때 -> DFS
  - 최단 거리 보장 X
  • ex) 조합, 순열, 그래프 탐색
• 모든 방향으로 한 단계씩 탐색 (큐 사용), 최단 거리를 구해야할 때 -> BFS
  - 최단 거리 보장 O
  • ex) 미로 탐색, 길찾기

DFS 문제 1

프로그래머스 네트워크 level 3

• 컴퓨터 개수 n과 연결 정보를 담은 2D 배열 computers가 주어진다.
• 연결된 컴퓨터들끼리 하나의 네트워크로 간주한다.
• 총 네트워크의 개수를 반환하라.

DFS로 풀어보기

def dfs(computers, visited, node):
    
    print("node", node)
    visited[node] = True
    
    for neighbor, isConnected in enumerate(computers[node]):
        if isConnected and not visited[neighbor]:
            print(f"d-dfs / ----> computers, {visited}, {neighbor}")
            dfs(computers, visited, neighbor)
            

def count_network(n, computers):
    visited = [False] * n
    cnt = 0
    for i in range(n):
        print("i", i)
        if not visited[i]: #방문하지 않은z 컴퓨터 하나씩 방문-점검
            print(f"c-dfs / ----> computers, {visited}, {i}")
            dfs(computers, visited, i)
            cnt += 1
            print(f"cnt+1 -> {cnt}")
            
    return cnt

원래 DFS 코드를 짜면서 항상 global 선언과 백트래킹을 했는데 이 문제는 노드가 연결되어 있으면 쭉 dfs가 실행되고 더 이상 연결되어 있지 않으면 dfs가 모두 실행되고 count_network() 함수로 돌아와 그 때 네트워크 개수를 1 추가하기 때문에 global 선언을 하지 않았고, 경로를 되돌아가지 않아도 되기 때문에 백트래킹을 하지 않았다.

DFS 문제 2

• begin 단어에서 words 단어 리스트에 있는 단어로, 한 개의 알파벳만 다르게 변경이 가능하다.
• 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution함수를 작성한다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없으며, begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0을 return 한다.

def dfs(begin, target, words, visited, depth):
    global answer # dfs에서 전역변수인 answer를 사용하기 위해 global선언. 선언하지 않으면 unbounded error가
    if begin == target:  # 5. 종료 조건 설정하기 (상단에)
        answer = min(answer, depth)
        return
    
    for i, word in enumerate(words):
        if not visited[i] and is_one_letter_different(begin, word):
            visited[i] = True
            dfs(word, target, words, visited, depth + 1)
            visited[i] = False  # 백트래킹

def is_one_letter_different(word1, word2):
    cnt = sum([1 for a, b in zip(word1, word2) if a != b])
    return cnt == 1

def solution(begin, target, words):
    global answer #solution에서도 answer를 전역변수로 선언해준다.
    if target not in words:ㄴ
        return 0
    
    answer = float('inf')  # 1. 최소 단계를 찾기 위해 초기값을 무한대로 설정
    visited = [False] * len(words) # 2. 체크 리스트만들기
    
    for i, word in enumerate(words):
        if is_one_letter_different(begin, word):
            visited[i] = True # 3. 체크리스트에 체크하기
            dfs(word, target, words, visited, 1)
            visited[i] = False  # 4. 백트래킹
            
    return answer if answer != float('inf') else 0

앞으로 DFS 문제를 풀 때에는 다음과 같은 규칙을 생각하며 풀어야겠다.

1. 정답의 초깃값 설정
2. 체크리스트 만들기 (visited = 1 체크)
3. 체크리스트에 체크하기
4. dfs 함수
5. 체크리스트에 해제하기 (visited = 0 백트래킹)

BFS 문제 1

내 캐릭터는 1,1 위치에 있고, 상대팀 진영은 5,5 위치에 있는 경우.

벽으로 막힌 공간은 가지 못하며 동서남북 방향으로 한 칸씩 이동해서 최단거리로 도착하기 위해 지나가야 하는 칸의 개수 최솟값을 return한다.

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로 개수
    m = len(maps)    #세로 개수
    
    route = deque()
    route.append((0, 0)) # 1. 시작점 추가하기
    
    dx = [-1, 0, 1, 0]  # 상하좌우 이동
    dy = [0, 1, 0, -1]
    
    while route:
        x, y = route.popleft() # 2. popleft로 현위치 가져오기
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < m and 0 <= ny < n and maps[nx][ny] == 1:  
                maps[nx][ny] = maps[x][y] + 1  # 4. 방문처리 & 거리저장
                route.append((nx, ny)) # 3. 벽이 아니고 조건에 맞는 길 추가
                
    return maps[m-1][n-1] if maps[m-1][n-1] > 1 else -1

BFS 풀 때에는 다음과 같은 규칙을 생각하며 풀어야겠다.

1. 시작점 추가하기
2. popleft로 현 위치 가져오기
3. 벽이 아니고 조건에 맞는 길 추가
4. 방문처리 & 거리저장