들어가기 전 사전 지식
스택 (Stack)
- FILO(선입후출) / LIFO(후입선출) 구조
- 파이썬에서의 사용
리스트 사용
- push :
append() - pop :
pop()
collections 모듈의 deque 자료구조 사용
<aside> 💡 deque (양방향 큐) - 스택과 큐의 장점을 모두 채택
- 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 빠름
- push :
append() - pop :
pop()
큐 (Queue)
- FIFO(선입선출) 구조
- 파이썬에서의 사용
- 리스트 사용
- enqueue :
append() - dequeue :
pop(0)
- enqueue :
- collections 모듈의 deque 자료구조 사용
- enqueue :
append() - dequeue :
popleft()
- enqueue :
- 리스트 사용
재귀 함수 (Recursive Function)
- 자기 자신을 다시 호출하는 함수
- 스택을 이용해 쌓이고 다음 함수 호출
- 스택 구조를 이용해야 하는 상당 수의 알고리즘은 재귀로 풀릴 수 있음
- 반복문을 통해 해결하는 것과 비교해 코드가 간결해지는 장점을 가짐
- 수학에서의 점화식과 같음
그래프 (Graph)
노드(node) or **정점(vertex)**과 **간선(edge)**으로 이루어짐
- G = (V, E)
두 노드가 인접(adjacent)한 형태
- 두 노드가 간선을 통해 이어져 있는 형태
그래프의 표현 방법 2가지 ( 방향 / 무방향 그래프 모두 적용 가능)
예시
인접 행렬 (Adjacency Matrix)
- 2차원 배열로 그래프의 연결 관계를 표현
- 높은 밀도 그래프( |E| ~= |V|^2 ) 나 두 정점을 연결하는 간선이 있는지를 빠르게 확인할 필요가 있을 때 효율적
인접 리스트 (Adjacency List)
- 연결 리스트로 그래프의 연결 관계를 표현
- 파이썬에서는 리스트의 append()를 이용하면 됨
- 작은 밀도 그래프( |E| << |V|^2 )에 대에 효율적
인접행렬과 리스트 방식의 차이점 정리
- 공간적 측면 : 리스트 > 행렬
- 시간적 측면 : 행렬 > 리스트
2차원 배열 형태와 그래프
- 이차원 배열 형태의 탐색 문제는 그래프로 생각하여 풀 때 쉽게 풀 수 있을 때가 많이 있다
DFS (Depth-First Search; 깊이 우선 탐색)
- 그래프의 깊은 곳으로의 탐색을 우선적으로 실행하는 탐색
- 스택 자료구조를 이용
- 시간 복잡도
- 세타(V + E)
- 재귀 호출 루프 수행에 걸리는 시간 세타(V)
- 재귀 내 인접 정점 검사 시간 세타(E)
- 재귀로 구현한 DFS는 컴퓨터 시스템 특성상 실제 수행 시간은 느려 질 수 있음
- 세타(V + E)
동작 과정
- 탐색 시작 노드를 스택에 push하고 방문 처리.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 push하고 방문 처리. 방문하지 않은 인접 노드가 없다면, 스택의 최상단 노드를 꺼냄.
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복 수행
<aside> 💡 방문 처리란?
- 스택에 중복 삽입되지 않도록 스택에 삽입된 노드를 체크하는 처리
</aside>
- 일반적으로 인접한 노드 중 방문하지 않은 노드가 여러개라면 번호가 낮은 순서부터 처리함
- 노드의 탐색 순서 : 스택에 들어간 순서
의사 코드
time = 0 // 시간 기록을 위한 전역 변수
DFS(G) // G: 무방향 그래프
for u in [각 정점들] // 각 정점들 초기화
u.color = WHITE // 탐색 상태, WHITE: 탐색 전
u.p = NIL // 직전 원소 속성
for u in [각 정점들] // *이 정점의 순서에 따라 방문 순서가 달라질 수 있다!
if u.color = WHITE // 아직 방문하지 않은 정점에 대해
DFS-VISIT(G, u) // 탐색 실행
DFS-VISIT(G, u)
time += 1
u.d = time // u에 방문 했을 때 시간 기록
u.color = GRAY // GRAY: 방문 처리
for v in [u의 인접 정점들]
if v.color == WHITE // 방문하지 않은 정점이면
v.p = u // 현재 정점을 직전 원소 속성으로 지정
DFS-VISIT(G, v) // 탐색 실행
u.color = BLACK // BLACK: 인접 정점까지 탐색 완전 종료
time += 1
u.f = time // u의 인접 정점 조사가 끝났을 때 시간 기록
- 직전원소 부분 그래프는 여러 개의 깊이 우선 트리로 구성될 수 있음
- 즉, 깊이 우선 포레스트를 형성
- 특성
- 깊이 우선 트리의 구조가 재귀 호출 구조를 따라 직전원소 부분 그래프가 트리들의 포레스트를 형성함
- 재귀 호출이 해당 정점의 인접 정점들을 검색하는 동안 호출되면 u = v.p고 이 역도 성립함
- 발견 시간과 종료 시간이 괄호 구조를 가짐 - (v)
- 정점 발견 : ‘(’
- 정점 탐색 종료 : ‘)’
- 그래프의 간선을 분류하는데 사용할 수 있음
- 깊이 우선 트리의 구조가 재귀 호출 구조를 따라 직전원소 부분 그래프가 트리들의 포레스트를 형성함
어떤 방향 그래프가 비순환이면, 깊이 우선 검색이 ‘역행‘ 간선을 만들지 않으며 그 역도 성립
네 가지 간선 정의
- 트리 간선(tree edge)
- 깊이 우선 포레스트에 있는 일반적인 간선
- 역행 간선(back edge)
- 깊이 우선 트리에서 정점을 조상에 연결하는 간선
- 자기 순환(self-loop) 간선은 역행 간선으로 간주함
- 순행 간선(forward edge)
- 깊이 우선 트리에서 정점을 자손에 연결하는 간선
- 교차 간선(cross edge)
- 나머지 모든 간선
- 하나의 정점이 또 다른 정점의 조상이 아니어야 함
- 서로 다른 깊이 우선 트리에 있는 두 정점 사이에 있을 수도 있음
분류
- WHITE는 트리 간선을 나타냄
- GRAY는 역행 간선을 나타냄
- BLACK은 순행 또는 교차 간선을 나타냄
구현
# 깊이 우선 탐색 함수 정의
def dfs(graph, node, vidited):
# 현재 노드를 방문 처리
visited[node] = True
# 탐색한 노드 출력
print(node, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[node]:
if not visited[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]
]
# 각 노드가 방문한 정보
visited = [False] * 9
# DFS 실행
dfs(graph, 1, visited)
BFS (Breadth-First Search; 너비 우선 탐색)
- 가장 단순한 그래프 탐색 알고리즘. 그래프 탐색 알고리즘의 원형.
- BFS 기반 알고리즘들
- Prim의 최소 신장 트리 알고리즘
- Dijkstra의 단일 출발 최단 경로 알고리즘
- BFS 기반 알고리즘들
- 그래프의 탐색 시작 노드에서 가까운 노드를 우선적으로 탐색
- 큐 자료구조 이용
- O(V + E)
- 초기화 하는데 필요한 시간 O(V)
- 인접 리스트 스캔에 필요한 시간 O(E)
동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복
- 노드의 탐색 순서 : 큐에 들어간 순서 (혹은 큐에서 나오는 순서)
의사 코드
BFS(G, s)
// 정점들 속성 초기화
for u in [s를 제외한 각각의 정점들]
u.color = WHITE // 탐색 상태. WHITE: 탐색 전
u.d = INF // 거리
u.p = NIL // 직전 원소 속성
// 시작 정점 속성 설정
s.color = GRAY // GRAY: 방문 처리
s.d = 0 .
s.p = NIL
Q = 0 // 큐 생성
ENQUEUE（Q.s） // 큐에 시작 정점 삽입
// 큐가 빌 때까지 반복 (탐색)
while Q != 0
u = DEQUEUE（Q） // 큐에서 정점 하나를 가져옴
for v in [u의 인접 정점들] // 해당 정점의 인접 정점들에 대해
if v.color == WHITE // 방문하지 않았다면
v.color = GRAY // 방문 처리
v.d = u.d + 1 // 거리 해당 정점 + 1
v.p = u // 부모 속성으로 해당 정점 속성 추가
ENQUEUE(v) // 큐에 삽입
u.color = BLACK // BLACK: 인접 정점까지 탐색 완전 종료
- 직전원소 부분 그래프는 너비 우선 트리가 된다
- 직전원소 부분 그래프는 하나의 트리를 형성한다.
구현
- deque 라이브러리를 사용하는 것이 좋음
from collections import deque
#BFS 메서드 정의
def bfs(graph, start_node, visited):
# 큐 구현을 위해 deque 라이브러리 사용
q = deque([start_node])
# 현재 노드 방문 처리
visited[start_node] = True
# 큐에 아무것도 없을 때까지 반복
while q:
# 큐에서 원소 하나 뽑기
node = q.popleft()
# 탐색한 노드 출력
print(node, end=' ')
# 해당 노드와 연결된, 아직 방문 안한 원고들을 큐에 삽입
for i in graph[node]:
if not visited[i]:
q.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]
]
# 각 노드가 방문한 정보
visited = [False] * 9
# BFS 실행
bfs(graph, 1, visited)
문제 풀이
음료수 얼려 먹기
N * M 크기의 얼음 틀이 있음.
- 구멍 뚤린 부분 : 0
- 칸막이가 있는 부분 : 1
구멍이 뚫혀 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결된 것으로 간주
이 때, 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개 수는?
예시
- 총 3개 아이스크림 생성
입력 조건
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어짐 (1 ≤ N, M ≤ 1,000)
- 두 번째 줄부터 N+1번 줄까지 얼음 틀의 형태가 주어짐
출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수를 출력
풀이
# 얼음틀 크기 입력 받음
n, m = map(int, input().split())
# 얼음틀 입력 받음
iceFrame=[]
for i in range(n):
iceFrame.append(list(map(int, input())))
# dfs
def dfs(graph, x, y):
# 탐색 범위를 벗어났다면 종료
if x < 0 or x >= n or y < 0 or y >= m:
return False
if graph[x][y] != 1: # 해당 노드에 방문하지 않았으면
graph[x][y] = 1 # 해당 공간을 막음으로 방문 처리
dfs(graph, x+1, y) # 상, 하, 좌, 우 재귀로 체크 연결 체크
dfs(graph, x, y+1)
dfs(graph, x-1, y)
dfs(graph, x, y-1)
return True # 아이스크림 공간 있음
return False # 아이스크림 공간 없음 (막힘)
# 가능한 아이스크림 공간 갯수 세기
cnt = 0
for i in range(n):
for j in range(m):
if dfs(iceFrame, i, j):
cnt += 1
print(cnt) # 갯수 출력
미로 탈출
N * M 크기의 직사각형 미로에서 괴물을 피해 탈출해야 한다.
- 현재 위치 : (1, 1)
- 출구 : (N, M)
- 한 번에 한 칸 이동
- 괴물 칸 : 0
- 괴물 없는 칸 : 1
미로를 탈출할 수 있는 최단 거리를 구해라. (시작 칸과 마지막 칸 갯수에 포함)
입력 조건
- 첫째 줄에 두 정수 N, M (4 ≤ N, M ≤ 200)이 주어짐
- 다음 N개 줄에 각각 M개의 정수로 미로의 정보가 주어짐. (공백 없이)
- 시작 칸과 마지막 칸은 항상 1임
출력 조건
- 최소 이동 칸의 갯수 출력
풀이
from collections import deque
# 미로 크기 입력
n, m = map(int, input().split())
# 미로 정보 입력
maze = []
for i in range(n):
maze.append(list(map(int, input())))
# 방향 정보 딕셔너리
dir = {'u': (-1, 0), 'd':(1, 0), 'l':(0, -1), 'r':(0, +1)}
# bfs
def bfs(graph, x, y):
q = deque()
q.append((x, y)) # 시작 위치 큐에 삽입
graph[x][y] = 1 # 괴물 위치로 바꿔 방문 처리
while q: # 큐가 빌 때까지
x, y = q.popleft() # 큐에서 현재 위치 빼기
for d in dir: # 상, 하, 좌, 우 확인
dx, dy = dir[d] # 다음 위치 지정
rx, ry = x + dx, y + dy
# 미로 안에 없다면 다음 조건 진행
if (rx < 0 or rx >=n or ry < 0 or ry >= m):
continue
# 값이 1이라면 (처음 위치는 재방문 하지만 상관없으므로 진행)
if graph[rx][ry] == 1:
q.append((rx, ry)) # 큐에 다음 위치로 넣기
graph[rx][ry] = graph[x][y] + 1 # 다음 위치의 거리로 현재 위치 거리에 + 1
return graph[n-1][m-1] # 마지막 위치에 거리를 반환
# 실행
print(bfs(maze, 0, 0))
마무리 정리
| DFS | BFS | |
|---|---|---|
| 동작 원리 | Stack | Queue |
| 구현 방법 | 재귀 함수 | deque 라이브러리 |
| 탐색 위치 | 스택에 넣을 때 | 큐에서 빼고 나서 |
- 수행 속도 측면에서 BFS > DFS이다
- DFS 스택 / BFS 큐를 외워보자
- 디스하면 뻐큐다~
- 기본적인 BFS / DFS 함수는 안보고도 구현할 정도로 암기하자
- 왜냐? 코테에 기본적으로 활용해야 하는 경우가 많거든~
DFS / BFS의 사용
- BFS는 주어진 출발점으로부터 최단 경로들을 발견하게 해줌
- DFS는 다른 알고리즘의 서브 루틴으로 많이 활용됨