[이론]파이썬 알고리즘 - DFS / BFS

1. 탐색 알고리즘

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 방법
• DFS / BFS는 그래프 탐색 알고리즘

2. 재귀함수

• 자기 자신을 다시 호출하는 함수
• 스택 대신 재귀함수를 사용해서 구현하는 경우도 많음
• 파이썬에서는 재귀함수 호출의 깊이제한이 있기 때문에 이를 신경써야 함
• 재귀함수 사용 시 종료 조건을 반드시 명시해야 함
  재귀함수의 예(팩토리얼 구현)

def factorial_recursion(n):
  if n<=1:
    return 1
  return n*factorial_recursion(n-1)

• 재귀함수로 구현할 수 있는 것은 반복문으로도 구현할 수 있음
• 실제 코딩테스트에서는 반복문이 조금 더 빠르게 동작하는 경우도 있음

3. DFS(Depth-First Search)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 동작과정
  -1. 탐색 시작 노드를 스택에 삽입하고 방문처리
  -2. 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  -3. 2의 과정을 더이상 수행할 수 없을 때까지 반복

예1)

def dfs(graph, v, visited):
  # 현재 노드를 방문처리
  visited[v]=True
  print(v,end=' ')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

# 각 노드가 연결된 정보를 표현(0번 인덱스는 무시)
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]
# 각 노드가 방문한 정보를 표현
visited=[False]*9

dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5

예2) 음료수 채우기

def dfs(x,y):
  # 주어진 범위를 벗어나면 즉시 종료
  if x<=-1 or x>=n or y<=-1 or y>=m-1:
    return False
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y]==0:
    # 해당 노드 방문 처리
    graph[x][y]=1
    # 해당 노드 상,하,좌,우 모두 재귀적으로 호출
    dfs(x-1,y)
    dfs(x,y-1)
    dfs(x+1,y)
    dfs(x,y+1)
    return True
  return False


n,m=map(int, input().split())

graph=[]
for i in range(n):
  graph.append(list(map(int, input())))
# 모든 노드에 대하여 음료수 채우기
result=0
for i in range(n):
  for j in range(m):
    # 현재 위치에서 DFS수행
    if dfs(i,j)==True:
      result+=1

print(result)

4. BFS(Breadth-First search)

• 너비 우선 탐색. 가까운 노드부터 우선적으로 탐색(=최단거리 구할 때 사용)
• 동작과정
  -1. 탐색 시작 노드를 큐에 삽입하고 방문처리
  -2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  -3. 더 이상 2의 과정을 수행할 수 없을 때까지 반복

예1)

from collections import deque
def bfs(graph, start, visited):
  # 시작 값으로 큐 초기화
  queue=deque([start])
  # 시작 노드 방문 처리
  visited[start]=True
  
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력
    v=queue.popleft()
    print(v, end=' ')
    # 방문하지 않은 인접 노드들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True

# 각 노드가 연결된 정보를 표현(0번 인덱스는 무시)
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]
# 각 노드가 방문한 정보를 표현

bfs(graph, 1, visited)
# 1 2 3 8 7 4 5 6

예2) 미로 탈출

from collections import deque

def bfs(x,y):
  # bfs이므로 큐 사용
  queue=deque()
  queue.append((x,y))
  # 큐가 빌 때까지 반복
  while queue:
    x,y=queue.popleft()
    # 현재 위치에서 상,하,좌,우 확인
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      # 공간을 벗어난 경우 무시
      if nx<0 or nx>=n or ny<0 or ny>=m:
        continue
      # 괴물이 있는 경우 무시
      if graph[nx][ny]==0:
        continue
      # 해당 노드를 처음 방문하는 경우에만 +1해서 최단기록
      if graph[nx][ny]==1:
        graph[nx][ny]=graph[x][y]+1
        queue.append((nx,ny))
  # 가장 오른쪽 아래까지의 최단거리 반환
  return graph[n-1][m-1]

n,m=map(int, input().split())

graph=[]
for i in range(n):
  graph.append(list(map(int, input())))

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

print(bfs(0,0))

예3) 특정 거리의 도시 찾기

from collections import deque

n,m,k,x=map(int,input().split())
# 도로 정보 입력 받기 위한 리스트. 인덱스가 도시 번호, 각 원소가 연결된 도시들
graph=[[] for _ in range(n+1)]
# 연결된 도시들 도로 정보
for _ in range(m):
  a,b=map(int,input().split())
  graph[a].append(b)
# 모든 도시에 대한 최단거리 초기화
distance=[-1]*(n+1)
# 출발 도시까지의 거리는 0
distance[x]=0

q=deque([x])
while q:
  now=q.popleft()
  # graph[now]는 현재 도시에서 갈 수 있는 모든 도시
  for next_node in graph[now]:
    # 각 도시를 확인해서 아직 방문하지 않은 도시라면
    if distance[next_node]==-1:
      # 최단거리를 갱신
      distance[next_node]=distance[now]+1
      q.append(next_node)

# 최단거리가 k인 모든 도시의 번호를 오름차순 출력
check=False
for i in range(1,n+1):
  if distance[i]==k:
    print(i)
    check=True
# 최단거리가 k인 도시가 없다면 -1 출력
if check==False:
  print(-1)

예4) 바이러스 증식

from collections import deque

n,k=map(int,input().split())

graph=[] # 전체 보드 정보
data=[] # 바이러스에 대한 튜플 형태 정보

for i in range(n):
  # 보드 정보를 한 줄 단위로 입력하고 
  graph.append(list(map(int,input().split())))
  #한 줄마다 정보 추출
  for j in range(n):
    # 해당 위치에 바이러스가 존재하는 경우
    if graph[i][j]!=0:
      # (바이러스 종류, 시간, 위치x, 위치y) 삽입
      data.append((graph[i][j], 0, i, j))
# 정렬 이후에 큐로 옮기기(낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q=deque(data)

target_s, target_x, target_y=map(int, input().split())

# 바이러스가 퍼져나갈 수 있는 4가지 위치
dx=[-1,0,1,0]
dy=[0,1,0,-1]

while q:
  virus, s, x, y=q.popleft()
  # 5초가 지나거나 큐가 빌 때까지 반복
  if s==target_s:
    break
   # 현재 위치에서 주변 4가지 위치를 각각 확인
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    # 현재 위치로 이동할 수 있는 경우
    if 0<=nx and nx<n and 0<=ny and ny<n:
      # 아직 방문하지 않았다면 그 위치에 바이러스 넣고 시간+1
      if graph[nx][ny]==0:
        graph[nx][ny]=virus
        q.append((virus, s+1, nx, ny))
print(graph[target_x-1][target_y-1])