Computer Science

[알고리즘] BFS/DFS 그리고 다익스트라 알고리즘 & 백트레킹

dog-pawwer 2024. 9. 18. 16:15
반응형

이전 포스팅을 참고

https://jinhos-devlog.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84-%ED%83%90%EC%83%89-Exhaustive-Search

 

✒️ 1. BFS / DFS


- 너비우선탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식
- 깊이우선탐색(Depth-First Search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식
- 길 찾기 등에 주로 쓰이는 알고리즘이다. (미로 등)

BFS / DFS

 

✒️ 2. BFS (너비 우선 탐색)


BFS는 그래프나 트리 구조에서 노드를 탐색할 때 같은 레벨의 노드들을 먼저 탐색하는 방법이다.

 

시작 정점을 방문 한 후 시작 정점에 인접한 모든 정점들을 우선 방문한다.
더 이상 방문 할 정점이 없으면 한 depth 내려가서 다시 인접한 모든 정점들을 우선 방문한다.

💡 BFS의 특징

큐(Queue)를 사용하여 구현한다.

시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문한다.
최단 경로 찾기 문제에 주로 사용된다.
메모리를 더 많이 사용할 수 있지만, 답이 되는 경로가 여러 개인 경우 최단경로임을 보장한다.

 

💡 아이디어

어떤 노드를 방문했었는지 여부를 반드시 검사(검사하지 않으면 무한루프)

visited = [] 로 놓는 편!

BFS는 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐 사용(FIFO) => deque 사용

DEQUE

💡 deque 사용법

from collections import deque

# deque를 사용
queue = deque()
queue.append(1)
queue.append(2)
queue.popleft()  # 1

💡 기본 템플릿

from collections import deque

def bfs(graph, start_node):
    visited = set([start_node])
    queue = deque([start_node])
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')  # 노드 방문 처리
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

 

💡 예시 문제

일단 2D 그리드나 매트릭스에서 상하좌우 이동을 처리할 때 매우 일반적이고 효율적인 방법으로

아래처럼 배열을 선언하는 방식을 알아두자.

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

 

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/159993

[풀이]

from collections import deque

def bfs(maps, start, end):
    n, m = len(maps), len(maps[0])
    queue = deque([(start[0], start[1], 0)])  # (x, y, distance)
    visited = [[False] * m for _ in range(n)]
    visited[start[0]][start[1]] = True
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while queue:
        x, y, dist = queue.popleft()
        
        if (x, y) == end:
            return dist
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X' and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))
    
    return -1  # 도달할 수 없는 경우

def solution(maps):
    n, m = len(maps), len(maps[0])
    start, lever, end = None, None, None
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'S':
                start = (i, j)
            elif maps[i][j] == 'L':
                lever = (i, j)
            elif maps[i][j] == 'E':
                end = (i, j)
    
    to_lever = bfs(maps, start, lever)
    if to_lever == -1:
        return -1
    
    to_exit = bfs(maps, lever, end)
    if to_exit == -1:
        return -1
    
    return to_lever + to_exit

 

✒️ 3. DFS (깊이 우선 탐색)


DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 방법이다.


시작 정점을 방문 한 후 자식을 모두 탐색한다.
이때 연결된 노드가 존재하지 않을 때까지 들어왔다면 한 단계 이전으로 돌아가 다시 알고리즘을 수행한다.

 

💡 DFS의 특징

스택(Stack)이나 재귀를 사용하여 구현한다.
그래프의 깊은 부분을 우선적으로 탐색하며, 다시 돌아와서 다른 경로를 탐색한다.
모든 노드를 방문하고자 할 때 주로 사용한다.

-> BFS에 비해 구현은 좀 더 간단하지만 느리다.
경로의 특징을 저장해야 할 때 유용하다.

 

💡 아이디어

재귀적으로 동작(재귀 혹은 스택)
어떤 노드를 방문했었는지 여부를 반드시 검사(검사하지 않으면 무한루프)

이 또한 visited = [] 로 놓는 편!

 

💡 기본 템플릿 : 재귀 사용

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')  # 노드 방문 처리
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# 사용 예
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs_recursive(graph, 'A')  # 출력: A B D E F C

 

💡 기본 템플릿 : 스택 사용

파이썬의 리스트(list)는 스택의 기능을 모두 수행할 수 있다. => push() , pop()

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')  # 노드 방문 처리
            
            # 인접 노드를 역순으로 스택에 추가 (순서를 맞추기 위해)
            stack.extend(reversed([n for n in graph[node] if n not in visited]))

# 사용 예
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs_iterative(graph, 'A')  # 출력: A C F E B D

 

💡 예시 문제

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/154540

[풀이]

def dfs(maps, x, y, n, m):
    if x < 0 or x >= n or y < 0 or y >= m or maps[x][y] == 'X':
        return 0
    
    food = int(maps[x][y])
    maps[x][y] = 'X'  # 방문 표시
    
    # 상하좌우 탐색
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = x + dx, y + dy
        food += dfs(maps, nx, ny, n, m)
    
    return food

def solution(maps):
    n, m = len(maps), len(maps[0])
    stays = []
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] != 'X':
                stays.append(dfs(maps, i, j, n, m))
    
    return sorted(stays) if stays else [-1]

 

✒️ 4. 다익스트라(Dijkstra) 알고리즘 - 최단거리


💡 다익스트라 알고리즘

다익스트라 알고리즘은 BFS의 변형으로 볼 수 있다. 

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

음의 가중치가 없는 그래프에서 사용된다.

 

💡 아이디어

1. 거리와 노드를 튜플로 저장: (distance, node)
2. 거리가 가장 짧은 노드가 자동으로 힙의 최상위에 위치하게 된다.
3. heappop()으로 가장 가까운 노드를 효율적으로 선택할 수 있다.

cf. MST(무방향 가중치 그래프에서 모든 노드를 연결하는 가장 최소 비용의 트리를 찾는 문제)의 해결 알고리즘인 Prim 알고리즘도 heapq를 사용한다.

=> bfs 와 무엇이 다른가?

=> 다익스트라나 Prim 알고리즘에서 deque가 아닌 heapq를 사용하는 핵심 이유는 "가중치가 있는" 그래프에서 "최소" 값을 효율적으로 찾아야 하기 때문

 

💡 heapq 사용법

최소 힙(min heap) 자료구조를 사용

import heapq

# 1. 힙 생성
heap = []

# 2. 힙에 원소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 2)

print("힙 상태:", heap)  # 출력: [1, 2, 3, 4]

# 3. 힙에서 원소 제거 (최소값 추출)
min_value = heapq.heappop(heap)
print("추출된 최소값:", min_value)  # 출력: 1
print("힙 상태:", heap)  # 출력: [2, 4, 3]

# 4. 힙의 최소값 확인 (제거하지 않음)
min_value = heap[0]
print("현재 최소값:", min_value)  # 출력: 2

# 5. 리스트를 힙으로 변환
numbers = [5, 7, 9, 1, 3]
heapq.heapify(numbers)
print("힙으로 변환된 리스트:", numbers)  # 출력: [1, 3, 9, 7, 5]

 

💡 기본 템플릿

import heapq  # 우선순위 큐 구현을 위한 heapq 모듈 임포트

def dijkstra(graph, start):
    # 시작 노드로부터 각 노드까지의 거리를 저장할 딕셔너리 초기화
    # 모든 노드의 거리를 무한대로 설정
    distances = {node: float('inf') for node in graph}
    # 시작 노드의 거리는 0으로 설정
    distances[start] = 0
    # 우선순위 큐 초기화: (거리, 노드) 튜플을 요소로 갖는 리스트
    queue = [(0, start)]

    while queue:
        # 가장 거리가 짧은 노드 정보 꺼내기
        current_distance, current_node = heapq.heappop(queue)

        # 현재 노드가 이미 처리된 노드라면 스킵
        # (더 짧은 경로를 통해 이미 처리된 경우)
        if current_distance > distances[current_node]:
            continue

        # 현재 노드와 연결된 다른 인접 노드들 확인
        for neighbor, weight in graph[current_node].items():
            # 인접 노드로 가는 새로운 거리 계산
            distance = current_distance + weight
            # 새로운 거리가 기존에 알려진 거리보다 짧은 경우 갱신
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                # 갱신된 노드 정보를 우선순위 큐에 추가
                heapq.heappush(queue, (distance, neighbor))

    # 모든 노드까지의 최단 거리 반환
    return distances

 

✒️ 5. 백트레킹


💡 백트레킹

백트래킹은 DFS를 기반으로 하지만, 유망하지 않은 경로를 조기에 차단하는 최적화 기법이다.

>> 무슨 뜻이면, 원하는 조건에 불일치 하면 이전 단계로 돌아가서 다음 경우의 수를 생각하는 방식이다.
DFS와 비슷하지만, DFS 는 가장 깊은 노드까지 무조건 탐색하지만,

백트레킹 방식은 불필요한 탐색을 하지 않고 바로 이전 단계로 넘어온다.

 

더욱 효율적이다.

 

💡 아이디어

def 재귀함수(n):
	if 정답이면 :
		출력 or 저장
	else : 정답이 아니면 :
		for 모든 자식 노드에 대해서:
			if 정답에 유망하다면(답의 가능성이 있으면) :
				자식노드로이동
				재귀함수(n+1)
				부모노드로 이동

 

위와 같이 DFS(재귀)에서 불필요한 탐색을 줄이기 위해 조건을 추가하는 방식!

 

💡 예시 문제

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12952

 

가장 유명한 N-Queen 문제이다.
간단히 설명하면 "N*N 보드에 서로 공격할 수 없는 N개의 퀸을 둘 수 있는 경우의 수" 를 구하면 된다.

[풀이]

def solve_n_queens(N):
    def is_safe(board, row, col):
        # 같은 열에 퀸이 있는지 확인
        for i in range(row):
            # 같은 열이거나 대각선 상에 있는지 확인
            if board[i] == col or \
               board[i] - i == col - row or \  # 왼쪽 위 대각선
               board[i] + i == col + row:      # 오른쪽 위 대각선
                return False
        return True

    def backtrack(row):
        # 모든 행에 퀸을 배치했다면 해를 찾은 것
        if row == N:
            return 1
        
        count = 0
        for col in range(N):
            if is_safe(board, row, col):
                board[row] = col  # 현재 위치에 퀸 배치
                count += backtrack(row + 1)  # 다음 행으로 이동
        return count

    # 각 행의 퀸 위치를 저장할 리스트 초기화
    board = [-1] * N
    return backtrack(0)  # 첫 번째 행부터 시작
반응형