참고
그래프 탐색 알고리즘 (그래프 : 여러 개체들이 연결되어 있는 자료구조)
대표적인 문제 유형
- 경로 탐색 유형(최단거리, 시간)
- 네트워크 유형(연결)
- 연결되어 있는 그룹의 개수
- 두 개체가 같은 네트워크 안에 있는지
- 조합 유형(모든 조합 만들기)
스택
먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
파이썬에서 스택은 단순히 리스트와 append(), pop()으로 구현 가능하다.
stack = []
stack.append(5)
stack.pop()
...
print(stack[::-1]) #최상단 원소부터 출력
print(stack) #최하단 원소부터 출력
큐
먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조. 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화할 수 있다.
from collections import deque
queue = deque()
queue.append(5)
queue.append(3)
queue.popleft()
queue.append(2)
queue.popleft()
print(queue) #먼저 들어온 순서대로 출력
queue.reverse() #역순으로 바꾸기
print(queue) #나중에 들어온 순서대로 출력리스트를 사용하고, pop() 메서드의 특정 위치를 지정해서 원소를 빼게되면 위치 조정도 필요하므로 O(n) 만큼의 시간복잡도가 들게된다. 그래서 리스트로도 구현할 수 있지만 비용적으로 deque 라이브러리를 사용하는 것이 낫다.
재귀함수
자기 자신을 다시 호출하는 함수.
재귀 함수를 문제 풀이에서 사용할 때는 재귀함수의 종료 조건을 반드시 명시해야 함.
def recursive_function(i):
if i == 100:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)#팩토리얼 구현
#반복
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
#재귀
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1)
유클리드 호제법: 두 개의 자연수에 대한 최대공약수를 구하는 알고리즘
- 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라 한다.
- A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
GCD(192, 162) = GCD(162, 30) = GCD(30, 12) = GCD(12, 6) = 6
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
DFS (깊이 우선 탐색)
- 스택 자료 구조나 재귀 함수를 사용
- 깊은 부분을 우선적으로 탐색
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
- 더 이상 2번 과정을 수행할 수 없을 때까지 반복한다.
def dfs(graph, v, visited):
#현재 노드 방문 처리
visited[v] = True
print(v, end= ' ')
#현재 노드와 인접한 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[], # 인덱스 0은 사용하지 않음
[2, 3, 8], # 1번 노드와 연결
[1, 7], # 2번 노드와 연결
[1, 4, 5], # 3번 노드와 연결
[3, 5], # 4번 노드와 연결
[3, 4], # 5번 노드와 연결
[7], # 6번 노드와 연결
[2, 6, 8], # 7번 노드와 연결
[1, 7] # 8번 노드와 연결
]
visited = [False] * 9 #인덱스 0은 사용하지 않음
dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5BFS (너비 우선 탐색)
- 순서가 보장되어야 하기 때문에 Queue나 LinkedList를 사용하는 것이 일반적
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
from collections import deque
def bfs(graph, start, visited):
#큐 구현
queue = deque([start])
#현재 노드를 방문 처리
visited[start] = True
#큐가 빌 때까지 반복
while queue:
#큐에서 하나 원소 뽑아서 출력
v = queue.popleft()
print(v, end = ' ')
#아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in graph[v]:
if not visited[v]:
queue.append(i)
visited[v] = True
graph = [
[], # 인덱스 0은 사용하지 않음
[2, 3, 8], # 1번 노드와 연결
[1, 7], # 2번 노드와 연결
[1, 4, 5], # 3번 노드와 연결
[3, 5], # 4번 노드와 연결
[3, 4], # 5번 노드와 연결
[7], # 6번 노드와 연결
[2, 6, 8], # 7번 노드와 연결
[1, 7] # 8번 노드와 연결
]
visited = [False] * 9 #인덱스 0은 사용하지 않음
bfs(graph, 1, visited)
# 1 2 3 8 7 4 5 6
예제1. 음료수 얼려 먹기
N x M 크기의 얼음틀. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1
구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되있는 것.
얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램
입력 예시
4 5
00110
00011
11111
00000
출력 예시
3
연결 요소 찾기 문제 유형
문제 풀이 아이디어: 상하좌우가 연결된 형태의 그래프로 생각. 특정 지점에서 bfs나 dfs 수행하며 이동가능한 모든 경로에 대해서 모두 방문 처리를 한다.
- 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있으면 해당 지점 방문
- 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 진행하는 과정을 반복하면 연결된 모든 지점을 방문할 수 있다.
- 모든 노드에 대해 1~2번의 과정을 반복하며 방문하지 않은 지점의 수를 카운트.
#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 + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
return True
return False
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int,input()))
result = 0
for i in range(n):
for j in range(m):
#현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result)dfs 함수에서 상하좌우 위치에 대해서 재귀적으로 호출하는 것은 return을 하지 않기 때문에 그냥 연결된 모든 노드에 대해서 방문처리를 위한 것이다. 특정 지점에서 처음 재귀가 호출될 때만 'return True'가 되는 것으로 한 덩이의 구멍이 있는 것을 체크한다.
예제 2. 미로 탈출
N x M 크기의 직사각형 형태의 미로. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.
시작 위치는 (1, 1)이고 미로의 출구는 (N, M)이며, 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.
이때 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구해라. 시작 칸과 마지막 칸을 모두 포함해서 칸 수를 계산한다. 시작 칸과 마지막 칸은 항상 1이다.
입력 예시
5 6
101010
111111
000001
111111
111111
출력 예시
10
문제 해결 아이디어
- BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.
- 상하좌우로 연결된 모든 노드로의 거리가 1로 동일하다.
- 따라서 (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.
#BFS 코드 구현
from collections import deque
def bfs(x, y):
queue = deque()
queue.append((x,y))
#큐가 빌 때까지 반복
while 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] = graph[x][y] + 1
queue.append((nx, ny))
#도착 지점인 가장 오른쪽 아래까지의 최단거리 반환
return graph[n-1][m-1]
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input()))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
print(bfs(0,0))