파이썬 DFS, BFS, 백트래킹 예제문제와 정리

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 6: PART 2. 알고리즘 유형 분석 - DFS, BFS, 백트래킹, 32강 ~ 36강 내용 요약입니다.

 

# 예제문제(1) 길찾기 문제
# 보통 위, 아래, 왼, 오 4방향이 많다.
# 체스 등 응용 문제도 있다.
# 방향값을 미리 코드로 짜두고 for문으로 순회하는 기법을 익혀두자

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
chk = [[False] * 100 for _ in range(100)]
N = int(input())

def is_valid_coord(y, x):
    return 0 <= y < N and 0 <= x < N

def bfs(start_y, start_x)
    q=deque()
    q.append((start_y, start_x))
    while len(q) > 0:
        y, x = q.popleft()
        chk[y][x] = True
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and not chk[ny][nx]:
                q.append((ny, nx))

 

# 백트래킹 Backtracking 퇴각검색
- 기본적으로 모든 경우를 탐색하며 DFS/BFS와 방식은 유사하다
- 백트래킹은 가지치기를 통해 탐색의 경우의 수를 줄인다는 차이다 있다
- 최악의 경우, 모든 경우를 다 살펴보게 될 수도 있지만 가능한 덜 보겠다는 전략
- '가망성이 없으면 가지 않는다'

 

# 예제문제(2) 백트래킹
# boj.kr/11724
# 연결 요소의 개수
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: x-1, map(int, input().split()))
    adj[a][b] = adj[b][a] = 1

ans = 0
chk = [False] * N

def dfs(now):
    for nxt in range(N):
        if adj[now][nxt] and not chk[nxt]:
            chk[nxt] = True
            dfs(nxt)

for i in range(N):
    if not chk[i]:
        ans += 1
        chk[i] = True
        dfs(i)

print(ans)

 

# 예제문제(3) 최단경로
# boj.kr/2178
# 미로탐색

from collections import deque

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
N, M = map(int, input().split())
board = [input() for _ in range(N)]

def is_valid_coord(y, x):
    return 0<=y<N and 0<=x<M

def bfs():
    chk = [[False] * M for _ in range(N)]
    chk[0][0] = True
    dq = deque()
    dq.append((0, 0, 1))
    while dq:
        y, x, d = dq.popleft()

        if y == N-1 and x == M-1:
            return d
        
        nd = d + 1
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and board[ny][nx] == '1' and not chk[ny][nx]:
                chk[ny][nx] = True
                dq.append((ny, nx, nd))

print(bfs())

 

# 정리
- 그래프는 node와 edge로 이루어져 있다
- 방향성과 순환성이 각각 있거나 없거나
- 둘 다 있으면 트리
- 수많은 그래프/트리 종류와 알고리즘들이 존재한다

# 그래프를 코드로 구현할 때는 2가지 방법이 있다
- 1. 인접행렬
- edge가 많은 그래프일 때 쓰는게 좋다
- edge 탐색이 빠르다
- 2. 인접리스트
- edge가 적은 그래프일 때 쓰는게 좋다
- 메모리를 적게 쓴다

# DFS, BFS, 백트래킹은 전부 완전탐색 알고리즘
- 최악의 경우 모든 노드를 탐색하는 것은 동일
- 최단거리를 구할 때는 BFS 사용
- DFS는 재귀(or 스택), BFS는 큐로 구현
- 가지치기를 하면 백트래킹