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

 

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

dfs와 bfs는 가장 흔히 사용되는 그래프 탐색 알고리즘이다.

 

 

알고 가야하는 두가지 자료 구조:

 

스택: 선입후출 / 입구와 출구가 동일한 형태

큐: 선입선출 / 입구와 출구가 모두 뚫려 있는 터널과 같은 형태. 

 

재귀 함수:

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

재귀 함수 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함. 

그렇지 않을 경우 함수가 무한히 호출될 수 있다.

 

재귀 함수를 이용하게 되면 마치 스택에 데이터를 넣었다가 꺼내는 것과 마찬가지로 각각의 함수에 대한 정보가 실제로 스택 프레임에 담기게 되어서 이렇게 차례대로 호출이 되었다가, 마지막에 호출되었던 함수부터 차례대로 종료되어 결과적으로 첫번째 호출했던 함수까지 종료되는 것을 알 수 있다.

 

수학적으로 정의된 점화식을 호출함으로서 훨씬더 직관적으로 확인 할 수 있는 코드를 작성 할 수 있다.

 

재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있습니다.

모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현 가능 / vice versa

 

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택프레임에 쌓인다.

그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많다.

 

 

DFS

(Depth First Search)

DFS는 깊이 우선 탐색 이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작과정은 :

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

 

BFS

(Breadth First Search)

BFS 는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.

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

BFS는 간선의 비용이 모두 동일 할 때 최단거리를 찾기위해 사용할 수 잇는 방법!

 

matrix[nx][ny] = matrix[x][y] +1 

등을 사용하면 각 원소의 값이 해당 원소에 도달하기까지 소요된 단계 수로 바뀐다. 아주 유용!

 

 

DFS 기본 유형

1

BFS 기본 유형

import sys
from collections import deque
input = sys.stdin.readline


# 입력
n, m, start = map(int, input().split())  # 임시


# 2차원 방향 배열 -메모리 초과 가능성-
graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1


# 1차원 방향 배열 -가공이 살짝 귀찮-
graph = []
for _ in range(n+1):
    graph.append([])
# or
graph = [[0] * (n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    # 양방향일 경우 둘다 쓰면 되고 아닐 경우 하나만
    graph[a].append(b)
    graph[b].append(a)


# 알고리즘 실행을 위한 방문 확인 리스트들
visited = [0] * (n + 1)
visit_list2 = [0] * (n + 1)


# 기본 bfs 함수 / 노드2노드 이동
# 큐에 시작 노드 넣어두기 / 여러개면 여러개 넣어두면 됌.
que = deque([start])
visited[start] = 1


def bfs():
    while que:
        vv = que.popleft()

        for i in range(1, n+1):
            # 방문 여부/ 갈 수 있는지 여부
            if visited[i] == 0 and graph[vv][i] == 1:

                que.append(i)
                visited[i] = 1
                #record[now+1] = record[now] + 1
                # 이를 통해 최단 소요 턴 표시 가능


# bfs 함수 2차원
# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 3차원의 경우 토마토 참고


def bfs_2d(r, c):
    # 이는 위처럼 따로 뺴도 됌.
    que = deque([])
    que.append([r, c])
    visited[r][c] = 1

    while que:
        [x, y] = que.popleft()
        # 방향의 개수에 따라 변경시키면 됌. 숨바꼭질 참고
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 역시나 갈 수 있냐, 방문 한 적이 없냐. 체크.
            if (0 <= nx < n) and (0 <= ny < m) and visited[nx][ny] != 1 and graph[nx][ny] != 0: #예시
                visited[nx][ny] = 1
                que.append([nx, ny])
                # maze[nx][ny] = maze[x][y] + 1


# 답은 알아서 가공 후 제출