[이것이 코딩테스트다] DFS / BFS

자료구조 기초

0. 자료구조, Data Structure
   데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.
   스택, 큐는 자료구조의 기초 개념이다.

1. 스택, Stack
   FILO(First In Last Out), 선입후출 구조이다.
   LIFO(Last In First Out), 후입선출 구조이다.

   # python으로 stack 구현
   stack = []
   stack.append(1) # 삽입
   stack.pop() # 삭제

2. 큐, Queue
   FIFO(First In First Out), 선입선출 구조이다.

   # python으로 queue 구현
   # [참고] python으로 queue를 구현할 때 deque 자료구조를 활용한다. 데이터 처리 속도가 리스트 자료형에 비해 효율적이고 queue 라이브러리를 이용하는 것보다 더 간단하다.
   from collections import deque
   queue = deque()
   queue.append(1) # 삽입
   queue.popleft() # 삭제

알고리즘 기초

1. 탐색, Search
   많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.
   대표적인 탐색 알고리즘에는 DFS, BFS가 있다.

2. 재귀 함수, Recursive Function
   자기 자신을 다시 호출하는 함수를 의미한다.
   언제 끝날지를 알려주는 종료 조건을 꼭 명시해야 한다.

DFS, Depth-First Search

• 깊이 우선 탐색
• 그래프에서 깊은 노드를 우선적으로 탐색하는 알고리즘
• 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘
• 동작원리: 스택
• 구현방법: 재귀 함수 이용
• 시간: O(N)

# 노드가 연결된 정보 표현된 리스트
graph = [
	[],
	[2, 3],
	[1],
	[4, 5],
	[3, 5],
	[3, 4]
]

# 노드의 방문여부 확인 리스트
visited = [False] * 5

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

dfs(graph, 1, visited) # 1에서 시작해서 dfs

BFS, Breadth First Search

• 너비 우선 탐색
• 그래프에서 가까운 노드부터 탐색하는 알고리즘
• 동작원리: 큐
• 구현방법: 큐 자료구조 이용
• 시간: O(N), 일반적인 경우 실제 수행시간은 DFS보다 좋다.

from collections import deque

# 노드가 연결된 정보 표현된 리스트
graph = [
	[],
	[2, 3],
	[1],
	[4, 5],
	[3, 5],
	[3, 4]
]

# 노드의 방문여부 확인 리스트
visited = [False] * 5

# BFS 메서드 정의
def bfs(graph, start, visited):
	queue = deque([v])		# Queue 구현을 위해 deque 라이브러리 사용
    visited[start] = True	# 현재 노드 방문 처리
   	
    while queue:			# Queue가 빌 때까지 반복
    	v = queue.popleft()
        print(v, ' ')
        
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
    

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

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

def dfs(x, y):
	if x <= -1 or x > n or y <= -1 y > m:
    	return False
    if graph[x][y] == 0:
    	graph[x][y] = 1
    	dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    return False

result = 0
for i in range(n):
	for j in range(m):
    	if dfs(i, j) == True:
        	result += 1
print(result)

실전문제 2, 미로 탈출

움직여야하는 최소 칸 수 -> BFS 알고리즘으로 접근해야 한다.

from collections import deque

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

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
	queue = deque()
    queue.append((x, y))
    
    while queue:	# queue가 빌 때까지 반복
    	x, y = queue.popleft()
        for i in range(4):
        	nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
            	continue
            if graph[nx][ny] == 0:
            	continue
            if graph[nx][ny] == 1:
            	graph[nx][ny] += 1
                queue.append((nx, ny))
    return graph[n-1][m-1]

bfs(0, 0)