DFS template
Recursive DFS Template
def dfs(node, state):
# 방문 처리
visited[node] = True
# 현재 노드에서 할 수 있는 작업 수행
process(node, state)
# 인접 노드 탐색
for next_node in graph[node]:
if not visited[next_node]:
dfs(next_node, new_state)
# 필요한 경우 백트래킹을 위해 방문 해제
visited[node] = False
# 그래프 초기화 및 방문 배열 선언
graph = {}
visited = {}
# 그래프 구성
# 예: graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
# 방문 배열 초기화
# 예: visited = {0: False, 1: False, 2: False}
# DFS 호출
# 예: dfs(start_node, initial_state)
Examples
Q. miro: find the shortest path
n, m = map(int, input().split())
miro_grid = []
for i in range(n):
# strip is used bc no space between input values
row = input().strip()
# need to wrap this with [ ] to avoid generator issue
miro_grid.append([int(char) for char in row])
# n is row AND m is col
visited = [[False]* m for _ in range(n)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
count = 1
min_distance = float('inf')
def dfs(row, col, count):
global min_distance
# 도착점에 도달했을 때
if row == n-1 and col == m-1:
min_distance = min(min_distance, count)
return
# 방문 처리
visited[row][col] = True
# 현재 위치에서 할 수 있는 작업 수행 -> 방향 탐색, 결과 갱신, etc.
for dx, dy in directions:
nx, ny = row + dx, col + dy
if is_valid(nx, ny):
# recursion
dfs(nx, ny, count + 1)
# 백트래킹 (방문 해제)
visited[row][col] = False
def is_valid(x, y):
return 0 <= x < n and 0 <= y < m and not visited[x][y] and miro_grid[x][y] == 1
dfs(0, 0, 1)
print(min_distance)Q. Baechoo
No need for backtracking for this question
B.C. we are solving for the problem of finding connected components in the grid
backtracking is "UNDO" the choice so you can explore other possibilities from the same starting point
def dfs(row, col, grid, visited, n, m):
directions = [(0,1), (0, -1), (1, 0), (-1, 0)]
visited[row][col] = True
for dx, dy in directions:
new_row, new_col = row + dx, col + dy
if 0 <= new_row < m and 0 <= new_col < n:
if not visited[new_row][new_col] and grid[new_row][new_col] == 1:
dfs(new_row, new_col, grid, visited, n, m)Q. Robot Vaccum
def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
n = len(room_map)
m = len(room_map[0])
visited = set()
# 0 = 북, 1 = 동, 2 = 남, 3 = 서
directions = [(-1,0), (0, 1), (1, 0), (0, -1)]
def turn_left(d):
return (d + 3) % 4
def explore(r, c, d):
for _ in range(4):
d = turn_left(d)
new_r, new_c = r + directions[d][0], c + directions[d][1]
# a. 왼쪽 방향에 아직 청소하지않은 공간이 존재한다면, 그 방향으로 회전후 한칸 전진후 1번부터 다시 진행한다.
if 0 <= new_r < n and 0 <= new_c < m and room_map[new_r][new_c] == 0 and (new_r, new_c) not in visited:
clean_dfs(new_r, new_c, d)
return True # 청소하지 않은 공간이 존재함
return False # 네방향 모두 이미 청소가 되어있거나 벽임
def clean_dfs(r, c, d):
# 1. 현재 위치를 청소한다.
if room_map[r][c] == 0 and (r, c) not in visited:
visited.add((r, c))
# 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. (using explore)
if not explore(r, c, d):
# 만약 네 방향 모두 청소가 이미 되어있거나 (in visited) OR 벽인경우
back_r, back_c = r - directions[d][0], c - directions[d][1]
# c. 후진후 2번으로 돌아가거나 d. 뒤쪽방향이 벽이라 후진도 할수 없는 경우 작동 끝
if room_map[back_r][back_c] == 0:
clean_dfs(back_r, back_c, d)
clean_dfs(r, c, d)
return len(visited)Backtracking
BFS (너비 우선 탐색)
BFS는 시작 노드로부터 가까운 노드부터 차례대로 방문하며, 모든 이웃을 큐에 넣은 후 다시는 방문하지 않습니다.
BFS는 각 노드를 한 번씩만 방문합니다. 한 노드를 방문했다면, 그 노드는 이미 최단 경로로 탐색된 것으로 간주되므로 다시 방문할 필요가 없습니다.
BFS는 레벨 별로 탐색하므로, 한 번 방문한 노드는 다시 방문할 이유가 없습니다.
그리고 BFS는 모든 가능한 경로를 동시에 탐색하기 때문에 "상태를 되돌리는" 백트래킹이 필요하지 않습니다.
DFS (깊이 우선 탐색)
DFS는 가능한 한 깊게 노드를 탐색하고, 더 이상 탐색할 경로가 없을 때 이전 분기점(노드)으로 돌아와 다른 경로를 탐색합니다.
이 때, 이전 노드로 돌아가 다른 경로를 시도할 때 백트래킹 이 필요합니다.
백트래킹은 현재 경로가 유망하지 않을 때 다른 선택지를 탐색할 수 있도록 이전 상태로 "되돌리는" 기법입니다. 따라서 DFS는 탐색 경로마다 방문했던 노드를 방문 해제하여, 다음 경로 탐색 시 그 노드를 재방문할 수 있게 합니다.
백트래킹의 필요성:
예를 들어, 미로 탐색 문제에서 다음과 같은 상황을 생각해 볼 수 있습니다:
한 노드에서 여러 방향으로 탐색을 시도하다가 막다른 길을 만났다고 가정합니다. 이 경우, 그 노드로 돌아와 다른 방향을 탐색해야 할 수 있습니다.
만약 방문한 노드를 방문 해제하지 않는다면, 다른 방향의 유효한 경로가 있음에도 불구하고 그 경로를 시도할 수 없게 됩니다. 즉, 올바른 해결책을 찾지 못할 수 있습니다.
백트래킹은 DFS가 다양한 가능성을 탐색할 수 있게 하며, 특히 "모든 가능한 해결책을 찾거나", "최적의 해결책을 찾는" 문제에서 매우 중요합니다. 이런 이유로 DFS에서는 방문 해제(백트래킹) 과정이 필수적입니다.
Iterative DFS Template
def iterative_dfs(start_x, start_y):
stack = [(start_x, start_y)]
visited = [[False]*m for _ in range(n)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while stack:
x, y = stack.pop()
if not visited[x][y]:
visited[x][y] = True
process(x, y) # 현재 위치에서의 처리 로직
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny] == 1:
stack.append((nx, ny))Note:
iterative dfs 는 backtracking 을 해서 풀어야 하는 문제를 풀기는 어렵다. 왜냐하면 visited 을 true 와 false 로 바꾸기 까다롭기때문이다. By creating a new visited set for the new path, you can solve it. HOWEVER, 이런경우 그냥 recursion 을 쓰거나 bfs 를 쓰는것이 더 나은 선택이다. 즉 shortest path 를 찾는경우 dfs 를 이용하지않는다. recursion으로는 가능하지만 그래도 bfs 를 이용하는게 나은경우가 대부분이다.
Examples
Q. Baechoo
def dfs_iterative(start, grid, visited, n, m):
directions = [(0,1), (0, -1), (1, 0), (-1, 0)]
visited[start[0]][start[1]] = True
# STACK
stack = [start]
while stack:
row, col = stack.pop()
for dx, dy in directions:
new_row, new_col = row + dx, col + dy
if 0 <= new_row < m and 0 <= new_col < n:
if not visited[new_row][new_col] and grid[new_row][new_col] == 1:
# dfs(new_row, new_col, grid, visited, n, m)
visited[new_row][new_col] = True
stack.append((new_row, new_col))
else:
return 1
test_cases = int(input())
for test in range(test_cases):
n, m, total = map(int, input().split())
grid = [[0] * n for _ in range(m)]
visited = [[False] * n for _ in range(m)]
for i in range(total):
# x = col, y = row
x, y = map(int, input().split())
grid[y][x] = 1
total_worm = 0
# 세로 row
for i in range(m):
# 가로 col
for j in range(n):
if grid[i][j] == 1 and not visited[i][j]:
total_worm += dfs_iterative((i, j) , grid, visited, n, m)
print(total_worm)