[DFS/BFS] DFS, BFS

그래프 탐색 알고리즘 : DFS/BFS

• 코딩 테스트에서 반드시 출제 되는 유형임

 

기본적으로 알아야 하는 배경지식

• 스택 자료구조
• 재귀
  • https://yeonco.tistory.com/35

재귀 완벽히 이해하기

 

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

• 어떤 노드에서 시작해서 답을 찾을 때까지 갈 수 있는 인접 노드가 존재한다면 그 노드로 탐색을 반복
• 계속해서 깊게 파고 내려가다가 더 이상 진행할 인접 노드가 없다면 올라와서 또 다시 다른 인접 노드로 탐색
• 스택 또는 재귀함수로 구현

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

DFS 코드 예제

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],                # 그래프는 1부터 시작하니까 비워둠
    [2,3,8],        # 1은 2, 3, 8과 연결되어 있음
    [1,7],            # 2는 1, 7과 연결
    [1,4,5],        # 3
    [3,5],            # 4
    [3,4],            # 5
    [7],            # 6
    [2,6,8],        # 7
    [1,7]            # 8은 1, 7과 연결됨
]
# 각 노드가 방문한 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9     # 1-8까지의 노드의 방문 여부를 체크하기 위함

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

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

 

< 코드 실행 흐름 >

예시를 예로 들어보면 1에서 시작하므로

1. visited[1] 의 인덱스를 True 처리한다
2. 1을 출력한다
3. 1과 연결된 2, 3, 8을 모두 탐색한다
   4. 숫자가 가장 작은 2부터 탐색하는데 2는 방문한 적이 없으므로 dfs를 다시 실행한다
   5. 2를 방문처리하고 1, 7 중에 탐색안한 7을 탐색
   6. 7을 탐색하니 2, 6, 8이 나오는데 2는 방문했으므로 6을 방문
   7. 6을 방문하니 7밖에 없는데 7은 이미 방문함 (전부 방문)
4. 7에서 8을 방문
5. 1로 가보니까 3을 방문하지 않음
6. 3은 1, 4, 5와 연결되어 있으므로 4 먼저 방문
7. 다음 5

 

BFS (Breath First Search, 너비 우선 탐색)

• 현재 노드에서 모든 인접 노드를 탐색하고 나서 그 다음 아래 계층으로 내려감
• 그래프에서 가까운 노드부터 우선적으로 탐색
• 큐로 구현
• 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편임

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

• 최단거리를 구할 때 쓰기 좋음
• 제일 짧은 거리부터 하나씩 늘려가며 도달 가능한 모든 노드를 탐색
• 탐색 과정에서 최초로 목표 노드에 도달했을 때가 최단거리임이 보장

BFS 코드 예제

# BFS 예제
from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

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

 

실전문제

 

길찾기 문제

from collections import deque

# 왼, 위, 오, 아래
dy = (0, 1, 0, -1)
dx = (-1, 0, 1, 0)

N = int(input())
chk = [[False] * N form _ in range(N)]

# 유효범위인지 확인
def is_vaild_coord(y, x):
    return 0 <= y < N and 0 <= x < N

# dfs
def dfs(y, x):
    if adj[y][x] == ans:
        return

    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]

        # 유효범위 내에 있으면 재탐색
        if is_valid_coord(ny, nx) and not chk[ny][nx]:
            chk[ny][nx] = True
            dfs(ny, nx)

# bfs
def bfs(sy, sx): # start y, x
    q = deque()
    chk[sy][sx] = True
    q.append((sy, sx))

    while len(q):
        y, x = q.popleft()
        if adj[y][x] == ans:
            return

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and not chk[ny][nx]:
                chk[ny][nx] = True
                q.append(ny, nx)

 

 

음료수 얼려 먹기

https://yeonco.tistory.com/36

[DFS/BFS] 음료수 얼려 먹기

 

미로 탈출

 

https://yeonco.tistory.com/37

[BFS] 미로 탈출

 

출처

이것이 코딩테스트다