5-2. DFS/BFS 탐색 알고리즘

교재 알고리즘 동작 과정 그림 참고하긔

1. DFS

✓ DFS란?

• 깊이 우선 탐색(Depth-First Search). 그래스에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조 기반 / 재귀함수 활용 구현↑
• 동작 과정 중 방문 처리: 스택에 한 번 삽입된 노드를 처리하지 않기 위한 동작
  
  탐색 순서: 1-2-7-6-8-3-4-5 (일반적으로 작은 수부터 방문)
  (탐색 한 노드로 돌아갈 때는 스택에서 해당 노드를 꺼낸다)

def dfs(graph, v, visited):
  #현재 노드 방문 처리
  visited[v] = True
  print(v, end=' ')
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:  #해당 노드를 방문하지 않았다면 재귀호출 방문
      dfg(graph, i, visited)
      
 graph= [
   [],  #노드는 1부터 시작이므로 리스트의 0번 인덱스는 비워둠
   [2,3,8],
   ...
 ]
 
 #각 노드가 방문된 정보를 리스트 자료형으로 표현
 visited = [False]*9 #0번 인덱스를 비우기위해 8+1개 선언
 
 dfs(graph,1,visited)

✓문제: 음료수 얼려 먹기

• 문제: NxM크기의 얼음틀 가운에 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫린 부분끼리 상하좌우가 붙어있으면 서로 연결되어 있다고 간주한다. 얼음틀에서 생성되는 아이스크림 수를 구하는 프로그램을 작성하라.
• key
  • 연결된 모든 노드를 찾기위해 깊이 우선 dfs알고리즘 사용하기
  • 0과 연결된 노드들은 방문처리하여 이후 중복 카운트 시키지 않도록 하기
  • 상하죄우의 노드를 확인할 때 재귀함수 호출하기

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

#2차원 리스트로 맵 정보 받기
graph = []
for i in range(n):
	graph.append(list(map(int, input())))

#DFS구현
def dfs(x,y):
  #범위를 벗어나면 즉시 종료
  if x<=-1 or x>=n or y<=-1 or y>=m:  #리스트이므로 인덱스 주의(0시작)
    return False:
  #아직 방문하지 않은 0이라면
  if graph[x][y]==0:
    graph[x][y] = 1  #해당 노드 방문 처리
    dfs(x-1,y)       #상하좌우 위치 재귀적으로 호출
    dfs(x+1,y)
    dfs(x,y-1)
    dfs(x,y+1)
    return True
  return False
  
#모든 노드(위치)에 음료수 채우기
result = 0
for i in range(n):
  for j in range(m):
    if dfs(n,m) == True:
      result += 1

print(result)

2. BFS

✓BFS란?

• 너비 우선 탐색(Breadth-First Serach) 가까운 노드부터 우선적으로 탐색
• 큐 자료형(선입선출) 기반
  • 동작 방식: 탐색 시작 노드를 큐에 넣고 방문 처리->큐에서 노드 꺼내 해당 노드 인접 노드 중 방문하지 않은 모든 걸 큐에 넣음 -> 반복
• 최단거리 구하기에 유용
  위 그림 bfs탐색순서: 1-2-3-8-7-4-5-6

from collections import deque

#bfs구현
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
        
graph= [
   [],  #노드는 1부터 시작이므로 리스트의 0번 인덱스는 비워둠
   [2,3,8],
   ...
 ]
 
 #각 노드가 방문된 정보를 리스트 자료형으로 표현
 visited = [False]*9 #0번 인덱스를 비우기위해 8+1개 선언
 
 bfs(graph,1,visited)

✓문제: 미로 탈출

• 문제: NxM크기 직사각형 미로에 갇혀있다. 현재 위치는(1,1) 출구는 (N,M)이다. 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 탈출을 위한 최단 경로 칸의 개수를 구하시오. 시작 칸과 마지막 칸도 개수에 포함된다.
• key
  • 최단 경로를 구해야 하므로 bfs알고리즘 사용
  • 경로에 개수+1하기
  • continue 처리해야하는 2가지 경우 생각하기

from collections import deque

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

#이동할 네 방향 정의
dx=[0,0,+1,-1]
dy=[-1,+1,0,0]

#bfs구현
def bfs(x,y):
  queue = deque()
  queue.append((x,y))
  
  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      #미로 찾기 공간 벗어나면 무시
      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  #카운트+1
        queue.append((nx,ny))
        
   return graph[n-1][m-1]
   
print(bfs(0,0))