[Computer Science] 자료구조 - 그래프 탐색 DFS, BFS

DFS(depth-first search) - 깊이우선탐색

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 
LIFO 스택 자료구조(혹은 재귀함수)를 이용

DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더이상 2번 과정을 수행할 수 없을 때까지 반복.

Backtracking 

• DFS에서 활용되는 방법, 노드가 있을만한 곳을 되돌아가서 모두 살펴본다는 개념
• 위의 그림처럼 DFS는 깊이우선적으로 탐색을 진행하고, 재귀적으로 아래에서부터 탐색하지 않은 정점이 있는지 확인하는 방법으로 되돌아가는 것에서 backtracking사용.
• 이로 말미암아 시간이 오래걸린다는 단점이 발생함. 최단거리를 찾는데 문제가 있음.

DFS 소스코드 예제

'''DFS 소스코드 예제'''
# DFS 메소드 함수
def dfs(graph, v, visited): # v는 탐색을 시작하는 노드드
  #현재노드를 방문 처리한다
  visited[v] = True
  print (v, end=' ')
  #현재노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]: # 인접한 노드가 방문되지 않은 상태라면
      dfs (graph, i, visited) # 재귀함수로 방문

# 인접노드 딕셔너리 형태로 표현
graph = {
    1: [2,3,4],
    2: [5],
    3: [6],
    4: [],
    5: [7],
    6: [5,7],
    7: [6]}

# 각 노드가 방문된 정보를 표현(1차원 리스트)하는 리스트 초기화
visited= [False]*8 # 노드의 개수 n+1 를 곱해주어야 한다.

# DFS 함수 호출
dfs(graph, 1, visited)

'''1 2 5 7 6 3 4'''

dfs 함수 구현 방법

(검정화살표 : 인접리스트, 초록화살표 : 재귀, 파랑화살표 : 스택)

1. 재귀적 함수 구현
   • 코드가 간결함
2. 스택 함수 구현
   • 위에서 아래로 코드를 해석하면 되어서 직관적이고 이해가 쉬움
   • 후입선출 개녕를 적용하여 마지막 삽임된 노드를 기준으로 깊이우선탐색을 진행
   • 재귀와 다르게 역순으로 진행
   • 실행속도가 재귀보다 빠름

dfs 활용의 예

• 가중 그래프의 최소 스패닝 트리 찾기
• 길 찾기
• 그래프에서 주기 감지
• 미로 문제

BFS(breadth-first search) - 너비우선탐색

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘,  
FIFO 큐 자료구조를 이용한다. 

 

순서 : S->1->2->3->4->5->6->7

BFS 동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 더이상 2번의 과정을 수행 할 수 없을 때까지 반복

시작 노드에서 제일 멀리 떨어진 노드를 가장 마지막에 구하는 방식이며. 이런 특징때문에 각 간선의 비용이 모두 동일한 상황에서 최단거리를 문제를 해결하기 위한 방식으로 사용되기도 한다.

 

BFS 소스코드 예제

'''BFS 소스코드 예제'''
from collections import deque

# bfs메소드 함수 정의
def bfs(graph, start, visited):
  # 큐 구현을 위해 deque라이브러리 사용
  queue = deque([start])
  # 현재노드를 방문처리
  visited[start] = True
  # 큐가 빌때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력하기 queue응 popleft사용
    v = queue.popleft()
    print(v, end=' ')
    # 아직 방문하지 않은 인접한 노드들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True # 들어온 노드들 모두 방문처리

graph = {
    1: [2,3,4],
    2: [5],
    3: [6],
    4: [],
    5: [7],
    6: [5,7],
    7: [6]}

# 각 노드가 방문한 정보를 표현, 초기화 (1차원 리스트)
visited = [False]*8

# bfs 함수 호출
bfs(graph, 1, visited)

bfs 활용의 예

• 길 찾기, 라우팅
• BitTorrent와 같은 P2P 네트워크에서 인접 노드 찾기
• 웹 크롤러
• 소셜 네트워크에서 멀리 떨어진 사람 찾기
• 그래프에서 주변 위치 찾기
• 네트워크에서 방송
• 그래프에서 주기 감지
• 연결된 구성 요소 찾기
• 몇 가지 이론적 그래프 문제 풀기

BFS와 DFS 비교

• DFS 장점
  • 찾는 노드의 depth가 깊을수록 빠르다.
  • 메모리를 적게 차지 한다.
• BFS 장점
  • 최단경로를 찾기 적합하다.
  • 찾는 노드가 인접한 경우 효과적이다.
• DFS 단점
  • 노드가 무한한 갯수로 존재하는 경우, 무한반복(무한루프)에 빠진다.
• BFS 단점
  • Queue를 이용해 노드를 저장하기 때문에 노드의 수가 많을수록 메모리를 많이 소비한다.

 

예시 문제 1.

'''음료수 얼려먹기 문제'''
'''
첫번째 줄에 얼음 들의 세로길이 n과 m이 주어진다. (n >=1 ,m <= 1000)
주번째 줄부터 n+1번째 줄까지 얼음틀의 형태가 주어진다.
이때 구멍이 뚫린 부분은 0, 그렇지 않으면 1
-- 한번에 만들수 있는 아이스크림의 개수는?
'''
# dfs를 사용할 수 있다. 

def dfs(x, y):
  # 주어진 범위를 벗어나면 False처리로 즉시 종료
  if x <= -1 or x>= n or y <=-1 or y>=m:
    return False
  # 현재 노드를 아직 방문하지 않았다면 = 0 
  if graph[x][y] == 0:
    #해당 노드를 방문처리 1
    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을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
  # input으로 입력을 받으면 int형으로 변환하여 매핑하면 graph에 정수형 리스트로 append할 수 있다.
  graph.append(list(map(int, input())))

#모든 노드위치에 대하여 음료수 채우기
result = 0
for i in range(n):
  for j in range(m):
    # n*m의 현재 위치에서 dfs 수행
    if dfs(i, j) == True: #dfs수행했을때 방문된것이라면 count+1해준다.
      result +=1

print(result)

'''
input
4 5
00110
00011
11111
00000

result = 3

'''

예시문제 2. 

'''미로 탈출 
n>= 4, m <=200
현재 위치는 (1, 1) 출구는 (n, m)위치
이동할 수 있는 칸수는 한번에 한칸씩
괴물이 있는 부분은 0, 없는 부분은 1 
탈출 하기 위한 최소칸의 개수( 칸을 셀때 시작 칸과 마지막 칸을 모두 포함해서 계산)
시작과 마지막 노드는 모두 1 '''
# bfs를 사용하여 풀이
from collections import deque

def bfs(x, y):
  queue = deque()
  queue.append((x,y))
  # 큐가 빌때까지 반복하기
  while queue:
    x, y = queue.popleft()
    # 현재 위치에서 4가지 방향으로 위치를 확인
    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
      # 괴물이 없는 길인경우 최단거리 기록하기
      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))

'''
input
5 6
101010
111111
000001
111111
111111

result
10
'''

---

2021.10.11 - [파이썬] - [Computer Science] 자료구조 - 그래프

 

---

ref. 

https://youtu.be/7C9RgOcvkvo