코딩 테스트 준비 기록 - Day 4
BFS / DFS Algorithm
탐색이란?
많은 양의 데이터 중 원하는 데이터를 찾는 과정
BFS / DFS : 대표적인 그래프 탐색 알고리즘
💡 반드시 알아야 할 자료구조 및 개념
- stack
- Last in First Out
- 입구와 출구가 동일한 형태
- 삽입과 삭제 연산으로 이루어졌으며 각각의 시간복잡도는 O(1)
- Python에서는 List 자료형을 Stack 처럼 사용 (append, pop)
- queue
- First in First Out
- 입구와 출구가 모두 뚫려있는 터널 같은 형태
- 삽입과 삭제 연산으로 이루어졌으며 각각의 시간복잡도는 O(1)
- Python에서는 Deque 자료형을 Queue 처럼 사용 (append, pop_left)
- 재귀 함수(Recursive Function)
- 자기 자신을 다시 호출하는 함수
❗재귀 함수의 종료조건을 명시하여 무한히 호출되는 문제를 막아야 한다. - 유클리드 호제법(최대 공약수 구하는 대표 알고리즘)
- 두 자연수 A,B(A>B)에 대해 A를 B로 나눈 나머지를 R이라고 하면 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.
- 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있으나, 다른 사람이 이해하기 어려울 수 있으므로 주의
- 반복문과 재귀 함수는 상호 변경 가능
- 컴퓨터가 재귀 함수를 여러번 호출하면 메모리 내부의 스택 프레임에 쌓임
- 스택을 사용해야할 때 (DFS) 재귀 함수를 이용하는 경우가 많음.
- 자기 자신을 다시 호출하는 함수
DFS
- 깊이를 우선으로 하여 탐색하는 알고리즘
- 스택 구조 OR 재귀 함수를 이용함
- 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에서 방문하지 않은 인접 노드가 하나라도 있으면 스택에 넣고 방문 처리, 없으면 스택에서 꺼냄.
- 2과정 반복
BFS
- 너비를 우선으로 하여 탐색하는 알고리즘 (graph 내에서 가까운 노드부터 탐색하는 알고리즘)
- Queue 자료구조 이용함
- 동작 과정
- 탐색 시작 노드를 queue에 담고 방문 처리
- 큐에서 노드를 1개 꺼내고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 모두 queue에 삽입하고 방문처리
- 2과정 반복
💡 문제 1. 음료수 얼려먹기
- 구분된 곳의 개수를 찾는 문제
- 탐색하는 dfs를 구현하고 이를 matrix 전체에 순차적으로 대입하여 방문처리가 되는 곳의 갯수 counting
- 문제 해결 코드
# 문제 조건 입력
n, m = map(int, input().split())
visited = [[False] * m for _ in range(n)]
# graph 입력
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [1,-1,0,0]
dy = [0,0,1,-1]
count = 0
# dfs 메소드 정의
def dfs(x, y):
# 범위 벗어나면 재귀 끝.
if x < 0 or x >= n or y < 0 or y >= m:
return False
# 첫 번째 노드 방문
if not graph[x][y]:
graph[x][y] = 1
# 상,하,좌,우의 노드가 방문 안되어 있으면 dfs 호출하여 방문하기
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
dfs(nx, ny)
return True
else:
return False
# N X M 행렬 돌면서 dfs 수행
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
count += 1
print(count)
https://github.com/ybkim-dev/algorithms/blob/master/DFSBFS/음료수%20얼려%20먹기%20with%20dfs.py
💡 문제 2. 미로 탈출
- (1,1)에서 (N,M)의 경로의 최소 칸의 갯수 구하기
- BFS를 사용하여 (간선의 weight 즉, 거리가 1로 동일하므로) 모든 노드의 최단거리 값을 구한다.
❗이동시 마다graph[nx][ny] = graph[x][y] + 1
- 문제 해결 코드
from collections import deque
# 문제 조건 입력
n, m = map(int, input().split())
# graph 입력
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
visited = [[False] * m for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x, y):
global count
queue = deque()
queue.append([0,0])
visited[0][0] = True
while queue:
v = queue.popleft()
for i in range(4):
nx = v[0] + dx[i]
ny = v[1] + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
else:
if visited[nx][ny] == False and graph[nx][ny] == 1:
queue.append([nx, ny])
graph[nx][ny] = graph[v[0]][v[1]] + 1
visited[nx][ny] = True
bfs(0,0)
print(graph[n-1][m-1])
https://github.com/ybkim-dev/algorithms/blob/master/DFSBFS/미로%20탈출.py
Author And Source
이 문제에 관하여(코딩 테스트 준비 기록 - Day 4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@arkeio/코딩-테스트-준비-기록-Day-4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)