탐색이란?
탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정을 말한다.
대표적으론 DFS, BFS가 있으며, 코딩테스트에서 매우 자주 등장하므로 반드시 숙지해야한다.
시작하기 전 반드시 알아야 할 자료구조 - 스택
- 먼저 들어 온 데이터가 나중에 나가는 선입후출의 자료구조
- 입구와 출구가 동일한 형태로 시각화 할 수 있다.
스택 구현 예제
stack = []
stack.append(5)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.appned(4)
stack.pop()
print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력
출력 ->
[1,3,5]
[5,3,1]시작하기 전 반드시 알아야 할 자료구조 - 큐
- 먼저 들어온 데이터가 먼저 나가는 선입선출의 자료구조
- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.
큐 구현 예제
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(1)
queue.append(7)
queue.popleft()
print(queue) # 먼저 들어온 순서대로
queue.reverse() # 역순으로
print(queue) # 나중에 들어온 순서대로
출력 ->
deque([3,1,7])
deque([7,1,3])재귀 함수 (Recursive Function)
- 자기 자신을 다시 호출하는 함수로 DFS를 실질적으로 구현할 때 자주 사용된다.
재귀 함수 예제
def recursive_function():
print('재귀 함수를 호출한다.')
recursive_function()
recursive_function()- 위의 코드는 무한히 실행되는데, 파이썬에선 재귀의 깊이 제한이 있어 시간이 지나면 오류가 발생한다.
- 문제풀이에서 재귀함수를 사용할 땐 종류조건을 반드시 명시해야 한다.
종료조건을 포함한 재귀 함수 예제
def recursive_function(i):
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: # 1!은 1이므로 1반환
return 1
return n * factorial_recursive(n-1)- 위 두 종류의 코드 모두 같은 결과를 갖는다.
재귀함수의 예 - 유클리드 호제법
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))DFS (Depth-First Search)
- 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적 동작 과정은 다음과 같다
- 탐색 시작 노드를 스택에 삽입하고 방문처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
-> 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5 순으로 탐색
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)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
dfs(graph, 1, visited)BFS (Breadth-First Search)
- 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘* 큐 자료구조를 이용하며, 구체적 동작 과정은 다음과 같다
- 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 2번을 수행할 수 없을 때까지 반복한다.
-> 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6
BFS 소스코드 예제
from collections import deque
def bfs(graph, start, visited):
# 큐 구현을 위해 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
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
bfs(graph, 1, visited)그래프 탐색 알고리즘 예제 1 <음료수 얼려먹기> (DFS)
- N x M 크기의 얼음틀이 있다. 구멍이 뚫린 곳은 0, 칸막이가 존재하면 1로 표시된다. 구멍이 뚫린 곳끼리 상하좌우로 붙은 경우 하나로 연결된 것으로 간주한다. 얼음틀의 모양이 주어졌을 때 생성되는 아이스크림의 개수를 구하는 프로그램을 작성하라
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
def dfs(x, y):
# 주어진 범위를 벗어나는 경우 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 방문하지 않았다면
if grapn[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)
- N x M 크기의 직사각형 형태의 미로에 갇혔다. 여러마리의 괴물이 존재하여 이를 피해 탈출해야 한다. 현 위치는 (1,1) 이며 출구는 (N,M)에 존재한다. 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어있다. 탈출을 위해 움직여햐 하는 최소칸의 개수를 구하라. 칸을 셀 때는 시작과 마지막 칸을 포함하여 계산하며 미로는 반드시 탈출할 수 있는 형태로 제시된다.
from collections import deque
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]
# BFS 소스코드 구현
def bfs(x, y):
queue = deque()
queue.append((x, y))
# 큐가 빌때까지 반복
while queue:
x, y = queue.popleft()
# 현 위치에서부터 4가지 방향으로 위치 확인
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
# 0 이면 괴물이기때문에 무시
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)) 
🔥 Feelings fade, results remain