DFS/BFS(그래프탐색)

탐색 / 정렬 문제

탐색 알고리즘 : 여러 항목 중 특정 한가지 항목의 존재 유무를 판별하거나, 어디에 위치해 있는지 찾기 위한 방법이다.

 

순차탐색

이진 탐색

그래프 탐색 - 그래프를 탐색하는 방법이다.

 

 

DFS ( Depth - First Search )
: 깊이 우선 탐색

 

BFS ( Breadth - First Search )

: 너비 우선 탐색

 

 

---

DFS ( Depth - First Search )

: 깊이 우선 탐색

: 그래프에서 깊은 부분을 우선적으로 탐색한다.

: 스택, 재귀함수를 이용한다.

: 미로 찾기 ( 벽에 닿았을때, 다시 뒤로 돌아야한다)

 

스택 ( Stack )

스택 ( Stack )

출처:https://velog.io/@tiiranocode

: 선입후출 / 후입선출

: 먼저 들어온 것은 나중에 나간다.

: 박스 쌓기와 같다.

 

# 스택 구현
stack = []

# 삽입(5)-삽입(2)-삽입(3)-삭제()-삽입(7)-삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.pop()
stack.append(7)
stack.pop()

print(stack) # 최하단부터 출력
>>
print(stack[::-1]) # 최상단부터 출력
>> 

 

 

재귀함수 ( Recursive Function )

 

재귀함수 ( Recursive Function )

: 자기 자신을 다시 호출하는 함수

: 무한루프이므로, 사용할 때는 종료조건을 명시하자.

ex) 팩토리얼 n! , 유클리드 호제법 (최대공약수 계산)

 

# 재귀함수를 이용한 n!
def factorial_recursive(n):
  # 0! = 1, 1!=1
  if n <= 1: 
    return 1
  
  # n! = n*(n-1)!
  return n*factorial_recursive(n-1)

 

출처: https://www.codesdope.com/course/algorithms-dfs/

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. Stack 의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 Stack 에 넣고 방문 처리를 한다.
방문하지 않은 인접 노드가 없으면 Stack 에서 최상단 노드를 꺼낸다.

3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

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

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

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

#정의된 dfs 함수 호출
dfs(graph,1,visited)

# 방문처리 되는 순서 = 스택에 들어간 순서
>> 1,2,6,4,5,3,7

 

---

DFS 문제 맛보기

 

섬의 연결 갯수

4963번: 섬의 개수

음료수 얼려먹기

def dfs(graph,v, visited):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    if not visited[v[0]][v[1]]:
        visited[v[0]][v[1]] = True
        for i in range(4):
            nx = v[0] + dx[i]
            ny = v[1] + dy[i]
            if 0<= nx< N and 0<= ny < M:
                if not visited[nx][ny] and graph[nx][ny] == 0:
                    dfs(graph,(nx,ny),visited)
        return True

    return False
 
N,M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

visited = [[False for i in range(M)] for j in range(N)]

result = 0

for i in range(N):
    for j in range(M):
        if graph[i][j] == 0 and not visited[i][j]:
            result += dfs(graph,(i,j), visited)

print(result)

 

 

 

 

 

 

 

---

BFS ( Breadth - First Search )

: 너비 우선 탐색

: 그래프에서 가까운 노드부터 우선적으로 탐색

: 큐를 이용한다.

: 미로 찾기의 최소경로 알고리즘, 웹 크롤링에 이용된다.

 

큐 ( Queue )

큐 ( Queue )

출처 : https://velog.io/@sbinha

: 선입선출

: 먼저 들어온것이 먼저 나간다.

: 놀이공원 줄 서기와 같다.

# 큐 구현을 위한 deque 라이브러리 이용
from collections import deque

queue = deque()

# 삽입(5)-삽입(3)-삽입(7)-삭제()-삽입(2)-삽입(1)-삭제()
queue.append(5)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(2)
queue.append(1)
queue.popleft()

print(queue)  #먼저 들어온 순서대로 출력
>> 

여러가지 방식의 Queue 구현

 

출처 : https://smlee729.github.io/

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

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[v] = True
                
graph = [
         [],
         [2,3,4],
         [1,5],
         [1,6,7],
         [1,8],
         [2,9],
         [3,10],
         [3],
         [4],
         [5],
         [6]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 11

# 정의된 BFS 메서드 호출
bfs(graph,1, visited) 

# 방문처리 되는 순서 = 스택에 들어간 순서
>> 1 2 3 4 5 6 7 8 9 10 

 

---

BFS 문제 맛보기

 

최소 경로 미로 찾기

2178번: 미로 탐색

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

참고 자료

 

DFS/BFS step 설명

DFS/BFS youtube 설명

이것이 코딩테스트다