dfs, bfs 정리

공부를 하다보니 DFS와 BFS를 좀 일반화하고, 단계별로 나눠서 기본형을 만들어 보면 좋겠다 싶어 정리한다

1. 전역 변수 선언:
   • visited: 각 노드의 방문 여부를 추적하는 배열 또는 맵.
   • dx, dy: x축과 y축 방향의 이동을 나타내는 배열. 상하좌우 또는 대각선 이동을 위해 설정.
2. DFS 함수 선언:
   • DFS 함수는 현재 노드의 좌표와 필요에 따라 추가적인 매개변수를 인자로 받자
3. 현재 노드 방문 처리:
   • 현재 노드를 visited 배열에 방문했다고 표시
4. 인접 노드 탐색:
   • 현재 노드에서 이동 가능한 모든 방향(dx, dy를 사용해서 nx,ny를 만들어주자)에 대해 반복문을 실행
   • 각 방향에 대해 새로운 위치 nx, ny를 계산
5. 탐색 조건 확인:
   • 새로운 위치 nx, ny가 탐색 영역 내에 있는지 확인
   • 해당 위치를 방문하지 않았는지 확인
   • 문제에 따라 추가적인 조건(내리막길만 이동 가능 한다던지..)을 확인
6. 재귀 호출:
   • 모든 조건을 만족하면, 새로운 위치에서 dfs(nx, ny)를 재귀적으로 호출
7. 종료 조건 및 결과 처리:
   • 필요에 따라 탐색이 끝났을 때 추가적인 처리를 수행하자. 예를 들어, 탐색 가능한 경로의 수를 세거나, 최단 거리를 계산하거나..

# 전역 변수 선언
N, M = ... # 탐색 영역의 크기
visited = [[False]*M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# DFS 함수 선언
def dfs(x, y):
    visited[x][y] = True  # 현재 노드 방문 처리
    for i in range(4):  # 인접 노드 탐색
        nx, ny = x + dx[i], y + dy[i]
        if 조건:  # 탐색 조건 확인
            dfs(nx, ny)  # 재귀 호출

# DFS 탐색 시작
for i in range(N):
    for j in range(M):
        if not visited[i][j]:  # 방문하지 않은 노드에 대해
            dfs(i, j)  # DFS 실행

 

이렇게 정리할수 있다. 기본적으로 이 형식을 따라 작성하고, 각 문제 형식마다 조금씩 바꿔보면 된다. 이때 전역변수를 어떻게 사용할지가 좀 관건인데, 배열을 여러번 사용해보며 비교해야할때가 있다. 그럴때는 global을 사용하는것도 고려해야한다.

 

또한, dfs로 주변에 연결된 배열칸의 갯수를 세는경우, 

def dfs(y,x,color):
  visited[y][x]=True
  count = 1
  for i in range(4):
    ny,nx = y+dy[i],x+dx[i]
    if 0<=ny<M and 0<=nx<N and not visited[ny][nx] and army[ny][nx]==color:
      count += dfs(ny,nx,color)
  return count

 

이런식으로 작성해보자.

 

 

BFS의 경우도 비슷하지만, 이때는 재귀가 아닌 큐를 사용하며, while문을 이용해 작성한다.

최단거리 문제나, 한번에 한단계씩 주변을 탐색하며 판별할때 사용하면 좋다.

1. 전역 변수 선언:
   • visited: 각 노드의 방문 여부를 추적하는 배열 또는 맵.
   • dx, dy: x축과 y축 방향의 이동을 나타내는 배열. 상하좌우 또는 대각선 이동을 위해 설정.
2. BFS 함수 선언:
   • BFS 함수는 시작 노드를 인자로 받자
   • 탐색을 위한 큐를 초기화하고, 시작 노드를 큐에 삽입하자.
3. 큐에서 노드 꺼내기:
   • 큐가 비어있지 않은 동안, 큐에서 노드를 하나 popleft 한다
4. 인접 노드 탐색:
   • 꺼낸 노드에서 이동 가능한 모든 방향(dx, dy를 사용)에 대해 반복문을 실행
   • 각 방향에 대해 새로운 위치 nx, ny를 계산(이건 dfs와 같다)
5. 탐색 조건 확인:
   • 새로운 위치 nx, ny가 탐색 영역 내에 있는지 확인
   • 해당 위치를 방문하지 않았는지 확인
   • 문제에 따라 추가적인 조건을 확인
6. 큐에 인접 노드 삽입:
   • 모든 조건을 만족하면, 새로운 위치를 큐에 삽입하고, 방문했다고 표시합니다.
7. 종료 조건 및 결과 처리:
   • 필요에 따라 BFS 탐색이 끝났을 때 추가적인 처리를 수행한다.
     예를 들어, 최단 거리를 계산한다던가, 탐색 가능한 경로의 수를 센다던가..

 

from collections import deque

# 전역 변수 선언
N, M = ... # 탐색 영역의 크기
visited = [[False]*M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 함수 선언
def bfs(start_x, start_y):
    queue = deque([(start_x, start_y)])
    visited[start_x][start_y] = True  # 시작 노드 방문 처리
    
    while queue:  # 큐가 비어있지 않는 동안
        x, y = queue.popleft()  # 큐에서 노드 꺼내기
        
        for i in range(4):  # 인접 노드 탐색
            nx, ny = x + dx[i], y + dy[i]
            if 조건:  # 탐색 조건 확인
                queue.append((nx, ny))  # 큐에 인접 노드 삽입
                visited[nx][ny] = True  # 방문 처리

 

dfs 와 비슷하면서도 확실히 bfs 만 사용해야 하는 문제가 있다.

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

7576번: 토마토

 

이런 문제를 보자. dfs로 접근하면 안되는 이유를 알수 있지 않는가?

한 스텝당 주변을 방문하면서 계산해야하는데, 재귀적으로 호출해버리면 문제의 요구사항과 완전 달라져버린다.

bfs는 종이에 물을 한방울 떨어뜨리면 주변으로 번져가는 느낌이라면, dfs는 물이 한 방향으로 계속해서 깊숙이 파고드는 느낌이다. 미로찾기같은걸 할때 물을 좌라락 채운다고 생각해보자.

 

dfs,bfs에 막연한 불안감을 가지고 있었는데, 일반화, 단계화를 거쳐 여러 문제를 풀어보니 역시 할만하다. 아니 그걸 넘어 재밌다! 강