DFS(Depth-First Search)/BFS(Breadth-First Search)란?

이것이 코딩 테스트다 with 파이썬 - Ch. 5 DFS/BFS를 공부하고 기록했습니다.

 

탐색(Search)

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

 

그래프, 트리 등 다양한 자료구조에 대한 탐색 알고리즘들은 코딩 테스트에서 흔하게 출제되기에 필수적으로 알아둬야한다. 해당 알고리즘을 활용해 다양한 솔루션들로 문제를 해결할 수 있기에 꼭 제대로 숙지하자.

 

DFS, BFS 알고리즘을 설명하기 이전, 스택(Stack)과 큐(Queue) 자료구조, 재귀에 대한 설명은 생략하고 진행한다.

 

DFS(Depth-First Search)

- 깊이 우선 탐색

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 스택 최상단 노드의 방문하지 않은 인접 노드들을 우선적으로 처리하는 방법

- 즉, 가능한 깊이 내려가면서 탐색을 진행하는 알고리즘

 

유용한 점

- 특정 경로를 찾는 것

- 그래프의 모든 노드를 방문하는 것

 

인접 리스트로 구현 코드

graphlist = [    # 인접리스트
	[2,3,8],
	[1,7],
	[1,4,5],
	[3,5],
	[3,4],
	[7],
	[2,6,8],
	[1,7]
]

visited = [False] * n	# 노드 방문여부 기록용 리스트

def dfs(v):				# 재귀 활용 코드
    visited[v] = True
    print(v)
    for i in graphlist[v]:
        if not visited[i]:
            dfs(i)

def dfs(v):    # 스택 자료구조 활용 코드
    stack = [v]
    visited[v] = True
    while stack:
    	val = stack.pop()
        if not visited[val]
            visited[val] = True
            print(val)
        for i in graphlist[val]:
            if not visited[i]:
            	stack.append(i)

 

 

인접 행렬로 구현 코드

graphmatrix = [
    [0, 1, 1, 1],  # 인접행렬
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [1, 1, 1, 0]
]

visited = [False] * n   # 노드 방문여부 기록용 리스트

def dfs(v):    			# 재귀 활용 코드
    visited[v] = True
    print(v)
    for i in graphmatrix[v]:
        if graphmatrix[v][i] == 1 and not visited[i]:  # 인접 노드 확인 및 방문 여부 확인
            dfs(i)
            
            
def dfs(v):				# 스택 자료구조 활용 코드
    stack = [v]
    visited[v] = True
    while stack:
    	val = stack.pop()
        if not visited[val]
            visited[val] = True
            print(val)
        for i in range(len(graphmatrix[val]), 0, -1):  
        # 노드 번호 기준 오름차순으로 찾기 탐색을 진행하기 위해 역순으로 스택에 넣어준다.
            if graphmatrix[val][i] == 1 and not visited[i]:
                stack.append(i)

 

 

BFS(Breath-First Search)

- 너비 우선 탐색

- 그래프에서 가까운 노드부터 탐색하는 알고리즘

- DFS와 반대

- 큐에서 출력되는 노드의 인접 노드들을 순서대로 처리

- 즉, 루트 노드로부터 가까운 노드들을 탐색하는 알고리즘

 

유용한 점

- 최단 거리 찾기 (인접한 노드들부터 탐색하기에 가장 최단, 빠른 경로를 찾을 수 밖에 없다)

 

 

인접 리스트로 구현 코드

from colletcions import deque

graphlist = [    # 인접리스트
	[2,3,8],
	[1,7],
	[1,4,5],
	[3,5],
	[3,4],
	[7],
	[2,6,8],
	[1,7]
]

visited = [False] * n	# 노드 방문여부 기록용 리스트

def bfs(v):        # Deque 활용 코드
    queue = deque()
    visited[v] = True
    while queue:
    	val = queue.popleft()  # 제일 앞 값 pop
        for i in graphlist[val]:
            if not visited[i]:
            	queue.append(i)
                visitedp[i] = True

 

인접 행렬로 구현 코드

graphmatrix = [
    [0, 1, 1, 1],  # 인접행렬
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [1, 1, 1, 0]
]

visited = [False] * n   # 노드 방문여부 기록용 리스트
          
def bfs(v):				# 덱 자료구조 활용 코드
    queue = deque()
    visited[v] = True
    while queue:
    	val = queue.popleft()
        for i in graphmatrix[val]:  
            if i == 1 and not visited[i]:
                queue.append(i)
                visited[i] = True

 

 

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

목표 : N X M 얼음 틀(0이 뚤려있는 거, 1이 막혀있는 거)이 있을때, 생성되는 아이스크림의 갯수를 출력해라.

특징 : 0으로 연결된 것끼리 상하좌우로 연결되어 있는 것으로 간주

입력 조건 : N, M(1 <= N, M <= 1,000)

 

Sol) 얼음 틀의 1이 연결된 덩어리를 구하는 문제다. BFS나 DFS를 통해 값이 1인 노드들을 찾아내면 된다. 문제를 풀기 전, DFS가 BFS보다 빠른 속도로 연결 덩어리를 찾아낼 수 있을 것이라고 판단했다.

+ 모든 빈칸에 대해 찾는 것이 아니라 구멍 틀이 있는 index에 대해서만 저장한 뒤 그 위치에 대해서만 DFS를 실행하는 것이 빠르다고 판단했다.

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

N, M = map(int, input().split()) # 개행문자 제거
ice = [list(map(int, input().strip())) for _ in range(N)]
point = []  # 1인 공간 기록용
visited = [[0] * M for _ in range(N)]
count = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(N):
    for j in range(M):
        if ice[i][j] == 0:
           point.append((i,j))

def dfs(x,y):         # DFS 로 푼 코드
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and ice[nx][ny] == 0:
            dfs(nx, ny)

def bfs(x,y):         # BFS로 푼 코드
    queue = deque()
    queue.append((x,y))
    visited[x][y] = 1
    while queue:
        sx, sy = queue.popleft()
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and ice[nx][ny] == 0:
                    queue.append((nx,ny))
                    visited[nx][ny] = 1

for x, y in point:
    if visited[x][y] == 0:   # dfs로 인해 이미 방문 처리가 안된 애들에 대해서만 실행
        # dfs(x,y)    # 여기에서 bfs로 실행할지 dfs로 실행할지 수정
        bfs(x,y)
        count += 1

print(count)