[Algorithm] 깊이 우선 탐색(DFS)/너비 우선 탐색(BFS)

bee·2023년 5월 23일

BFS DFS algorithm python 깊이우선탐색 너비우선탐색 탐색

Algorithm

목록 보기

6/8

탐색 (Search)

: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 '탐색'을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로, 코딩테스트에서도 자주 출제되는 유형인 DFS와 BFS에 대해 알아보고자 한다. 일단, DFS와 BFS를 이해하기 위해서는 기본 자료구조인 '스택'과 '큐' 그리고 '재귀함수'에 대해 알고 있어야 한다.

스택과 큐, 재귀함수에 대한 설명은 아래 링크에 따로 정리해두었으니 참고하도록 하자.

자료구조 - 스택 (Stack)
자료구조 - 큐 (Queue)
[Python - 재귀함수 (Recursive function)]

그래프 탐색

: 하나의 노드를 시작으로 다수의 노드를 방문하는 것

✓ 노드 (Node) = 정점(Vertex)

: 특정 지점

✓ 간선 (Edge)

: 노드와 노드를 연결하는 선

그래프 표현 방법

1. 인접 행렬 (Adjacency Matrix)

: 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

연결되지 않은 노드끼리는 '무한의 비용'이라고 작성한다.
모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리 측면에서 비효율적이다.
원하는 정보를 얻기 위해서 행렬의 해당 위치만 찾으면 되기 때문에 속도가 빠르다.

## 인접 행렬 방식 예제
INF = 999999999 # 연결되지 않은 노드에 대한 무한의 비용 선언

graph = [
	[0, 7, 5], 
	[7, 0, INf],
    [5, INF, 0]]

print(graph)

→ [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

2. 인접 리스트 (Adjacency List)

: 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식

'연결 리스트'라는 자료구조를 이용해서 구현한다.
(C++, Java 등에서는 라이브러리 제공. Python에서는 리스트 자료형 활용)
연결된 정보만을 젖아하기 때문에 메모리 측면에서 효율적이다.
원하는 정보를 얻기 위해서 연결된 데이터를 하나씩 확인해야 하기 때문에 속도가 느리다.

## 인접 리스트 방식 예제
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보(노드, 거리) 저장
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보(노드, 거리) 저장
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보(노드, 거리) 저장
graph[2].append((0, 5))

print(graph)

→ [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

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

개념

: 그래프에서 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘

특징

스택 자료구조를 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용해서 더 간결하게 나타낼 수 있다.
인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.

시간복잡도

데이터의 개수가 $N$ 개인 경우 시간 복잡도 : $O(N)$

동작원리

탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

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

 방문처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것

아래 그림으로 좀 더 자세히 살펴보자. 아래의 그래프에서 회색 노드는 방문 처리된 노드, 하늘색 노드는 현재 처리하는 스택의 최상단 노드이다.

위 그림을 코드로 구현해보자.

# DFS 메서드 정의
def dfs(graph, v, visited):
	visited[v] = True # 현재 노드를 방문 처리
    print(v, end = ' ') # 탐색된 노드 출력
    
    for i in graph[v]: # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    	if not visited[i]: # i번째 노드가 방문하지 않은 인접노드인 경우
        	dfs(graph, i, visited)
            
# 각 노드가 연결된 정보를 2차원 리스트 자료형으로 표현
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드의 방문 정보 False로 초기화 (1차원 리스트로 표현)
visited = [False] * 9

# DFS 함수 호출 (v : 최상단 노드)
dfs(graph, 1, visited)

→ 1 2 7 6 8 3 4 5

BFS (너비 우선 탐색; Breadth-First Search)

개념

: 가까운 노드부터 탐색하는 알고리즘

특징

큐 자료구조를 이용한다.
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면, 먼저 들어온 것이 먼저 나가게 되면서 가까운 노드부터 탐색을 진행하게 된다.
DFS와 마찬가지로 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정한다.

시간복잡도

데이터의 개수가 $N$ 인 경우 시간복잡도 : $O(N)$
(일반적으로 실제 수행 시간이 DFS 보다 효율적이다.)

동작원리

탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
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[i] = True # 방문처리
        
# 각 노드가 연결된 정보를 2차원 리스트 자료형으로 표현
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드의 방문 정보 False로 초기화 (1차원 리스트로 표현)
visited = [False] * 9

# BFS 함수 호출 (start : 시작 노드)
Bfs(graph, 1, visited)

→ 1 2 3 8 7 4 5 6

실습

실전문제 1. 음료수 얼려 먹기 (DFS)

구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된 N*M 크기의 얼음틀이 있다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

	 💡 해결 아이디어 
     1. 특정 노드의 주변 상, 하, 좌, 우를 살펴본 뒤 주변 노드 중 값이 0이면서 아직 방문하지 않은 노드가 있다면 해당 노드를 방문한다.
     2. 방문한 노드에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 노드를 방문할 수 있다.
     3. 1번과 2번 과정을 모든 노드에 반복하며 방문하지 않은 노드의 개수를 센다.

<## 모범답안
n, m = map(int, input().split())
ice = [list(map(int, input())) for _ in range(n)]

def dfs(x, y):
    
    # 주어진 얼음틀의 범위를 벗어나는 경우 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m: 
        return False
    
    # 현재 노드를 아직 방문하지 않았다면
    if ice[x][y] == 0:
        ice[x][y] = 1 # 해당 노드 방문처리
        
        # 상,하,좌,우의 위치도 모두 재귀적으로 호출(리턴값을 사용하지 않기 때문에 단순히 연결된 모든 노드에 대해서 방문처리를 하기 위한 목적으로 수행된다)
        dfs(x-1, y) # 현재 노드 기준 '왼쪽'방향 탐색
        dfs(x, y-1) # 현재 노드 기준 '아래쪽'방향 탐색
        dfs(x+1, y) # 현재 노드 기준 '오른쪽'방향 탐색
        dfs(x, y+1) # 현재 노드 기준 '위쪽'방향 탐색
        
        return True # 현재 위치에서 처음 DFS가 수행 => True
   
    # 얼음틀에 1밖에 없을때 즉시 종료
    return False


cnt = 0 # 카운트 할 아이스크림 개수

# 모든 노드에 대해서 음료수 채우기
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True: # 현재 위치가 처음으로 방문처리된 노드라면
            cnt += 1 # 아이스크림 개수 카운트

# 결과출력
print(cnt)

4 5
00110
00011
11111
00000

📌 KEY POINT

모범답안에서 가장 헷갈렸던 부분이 바로 이 부분이었다.

cnt = 0 # 카운트 할 아이스크림 개수

# 모든 노드에 대해서 음료수 채우기
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True: # 현재 위치가 처음으로 방문처리된 노드라면
            cnt += 1 # 아이스크림 개수 카운트

내가 이해가 안됐던 부분은 'dfs 메소드에 따라 방문처리된 노드가 여러개일 테고, 그렇게 되면 만들어지는 아이스크림 개수가 존재하는 노드만큼 많아지지 않을까?' 였다.
하지만 DFS 메소드 부분을 잘 살펴보면,

DFS가 한 번 수행되면 현재 노드와 연결된 모든 노드들도 각각 확인하면서 방문처리 할 수 있도록 하고, 시작노드가 방문처리 되었다면(처음 방문하는 것이라면) 그때만 카운트하는 방식이다.
상,하,좌,우의 위치도 모두 재귀적으로 호출하는 부분은 리턴값을 사용하지 않기 때문에 단순히 연결된 모든 노드에 대해서 방문처리를 하기 위한 목적으로 수행된다. 즉, 시작노드에 따라서 상, 하, 좌, 우 노드 모두 따로따로 방문처리 한 리턴값을 반환하는 것이 아니라, 상, 하, 좌, 우 모두 0인 경우 연결된 시작노드에 대해서만 '대표적으로' 방문처리 한 리턴값(True 또는 1)을 반환하는 것이다.

실전문제 2. 미로 탈출

N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로가 반드시 탈출할 수 있는 형태로 제시될 때, 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. (칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산하며, 시작 칸과 마지막 칸은 항상 1이다.)

	💡 해결 아이디어
    1. 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하는 방법인 BFS를 사용한다.
    2. (1, 1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다. 
    3. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.

## 모범답안
from collections import deque

n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]

# 이동할 네 방향 정의 (좌, 우, 하, 상)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# bfs : 간선의 비용이 모두 같을 때 최단거리를 탐색하기 위해 사용할 수 있는 알고리즘
def bfs(x, y):
    
    queue = deque()
    queue.append((x, y))
    
    # 큐가 빌 때 까지 반복
    while queue:
        x, y = queue.popleft()
        
        # 현재 위치에서 상,하,좌,우 방향으로 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 미로를 벗어난 경우 무시
            if nx < 0 or ny < 0 or nx >= n or ny >= m :
                continue
                
            # 괴물 때문이 이동할 수 없는 경우 무시
            if maze[nx][ny] == 0:
                continue
                
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1 # 바로 직전 노드에서의 최단거리값에 1을 더한 값 = 지금까지 온 최단거리
                queue.append((nx, ny))
                
    # 가장 오른쪽 아래(출구)까지의 최단 거리 반환
    return maze[n-1][m-1]

# 결과출력
print(bfs(0, 0))

5 6
101010
111111
000001
111111
111111

🔗 References

이것이 취업을 위한 코딩 테스트다 with 파이썬

bee

벌집처럼 밀도있게 차곡차곡 쌓아나가는중

이전 포스트

[Algorithm] 동적계획법(DP: Dynamic Programming)

다음 포스트

[Algorithm] 깊이 우선 탐색(DFS)/너비 우선 탐색(BFS)

Algorithm

탐색 (Search)

그래프 탐색

✓ 노드 (Node) = 정점(Vertex)

✓ 간선 (Edge)

그래프 표현 방법

1. 인접 행렬 (Adjacency Matrix)

2. 인접 리스트 (Adjacency List)

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

개념

특징

시간복잡도

동작원리

BFS (너비 우선 탐색; Breadth-First Search)

개념

특징

시간복잡도

동작원리

실습

실전문제 1. 음료수 얼려 먹기 (DFS)

📌 KEY POINT

실전문제 2. 미로 탈출

🔗 References

[Algorithm] 동적계획법(DP: Dynamic Programming)

[Algorithm] 구현 (Implementation)

0개의 댓글