나동빈 님의 '이것이 코딩테스트다'를 공부하고 작성한 글.
그래프 탐색 알고리즘: DFS/BFS
- 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있음
- DFS/BFS는 단골 출제 유형! 문제 많이 풀어야 됨.
스택 자료구조
- 먼저 들어온 데이터가 나중에 나가는 자료구조 (LIFO)
- 입구, 출구가 동일한 형태로 스택을 시각화 가능.
stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력
##
[5, 2, 3, 1]
[1, 3, 2, 5]큐 자료구조
- 먼저 들어 온 데이터가 먼저 나가는 형식(FIFO)의 자료구조
- 입구 출구가 모두 뚫려있는 터널 형태
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
## 결과 값
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])재귀함수
- 자기 자신을 다시 호출하는 함수
- 종료 조건을 반드시 명시해야함.
def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i== 100:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다')
recursive_function(1)팩토리얼 예제
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n + 1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1 이하인 경우 1을 반환
return 1
# n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n - 1)
# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))최대공약수 계산 (유클리드 호제법) 예제
유클리드 호제법
- 두 자연수에 대한 최대공약수를 구하는 대표적 알고리즘
- 두 자연수 A,B에 대해 (A>B) A를 B로 나눈 나머지를 R
- A와 BA의 최대공약수는 B와 R의 최대공약수와 같음
- 재귀함수로 작성 가능
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))재귀 함수 사용시 유의 사항
- 복잡한 알고리즘을 간결하게 작성 가능 but, 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있음.
- 모든 재귀함수는 반복문을 이용하여 동일 기능 구현 가능
- 컴퓨터가 함수를 연속적으로 호출할 때, 컴퓨터 메모리 내부의 스택 프레임에 쌓임.->스택을 사용해야 할 때, 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많음.
DFS(Depth-First Search)
- 깊이 우선 탐색. 그래프에서 깊은 곳을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(or 재귀함수)를 이용
- 탐색 시작 노드를 스택에 삽입. 방문 처리를 함
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.
DFS 동작 예시
방문 기준: 번호가 낮은 인접 노드부터
# DFS 함수 정의
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8], #1번 노드와 연결된 노드들
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)BFS (Breadth-First Search)
- 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- BFS는 큐 자료구조를 이용
- 탐색 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다
방문 기준: 번호가 낮은 인접 노드부터!
from collections import deque
# BFS 함수 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
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]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)<문제> 음료수 얼려 먹기
- N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
- 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
- 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
- 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다
출제자 풀이
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
# 해당 노드 방문 처리
graph[x][y] = 1
# 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
# 방문 처리를 위한 코드
return True
else:
return False
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True: # 처음 방문하는 노드가 0인 경우 result+=1 처리
result += 1
print(result) # 정답 출력
<문제> 미로 탈출
- 동빈이는 N × M 크기의 직사각형 형태의 미로에 갇혔다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다
- 동빈이의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다.
- 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다
- 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다
#출제자 풀이
import sys
from collections import deque
n,m=map(int,sys.stdin.readline().split())
graph=[]
for i 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:
x,y=queue.popleft() # 큐에서 최근에 들어간 원소 꺼냄.
for i in range(4): # 원소의 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]=graph[x][y]+1 # 노드까지 거리 기록.
queue.append([nx,ny])
return graph[n-1][m-1]
print(bfs(0,0))
- queue가 빌 때까지 반복한다는 뜻이 정확히 이해가 안됨.. bfs dfs 열심히 풀어야 할 듯
공부방