Intro
탐색 ⇒ 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
가장 대표적 탐색 알고리즘 → DFS & BFS
STACK 스택
- 박스 쌓기에 비유할 수 있다. 선입 후출 FILO(First In Last Out)
삽입(5) → 삽입(2) → 삽입(3) → 삽입(7) → 삭제 () → 삽입(1) → 삽입(4) → 삭제 ()
# stack list로 구현
# top은 가장 위에 있는 원소의 인덱스나 원소를 저장한다.
s = []
s.append(5)
s.append(2)
s.append(3)
s.append(7)
print(s)
print(s.pop())
s.append(1)
s.append(4)
print(s.pop())
print(s)
top = s[-1]
print(top)
⇒ 결론은 list로 스택을 모사할 수 있다. 로직만 알고 있으면 뭐가 왼쪽에 있건 오른쪽에 있건 다르게 stack을 짜서 이용할 수 있다.
QUEUE 큐
⇒ 큐는 대기 줄에 비유할 수 있다. 우리가 흔히 놀이공원에 입장하기 위해 줄을 설 때, 가장 먼저 온 사람이 가장 먼저 들어가고 가장 먼저 나가게 된다.
- 선입선출 FIFO(FIRST IN FIRST OUT)
삽입(5) → 삽입(2) → 삽입(3) → 삽입(7) → 삭제 () → 삽입(1) → 삽입(4) → 삭제 ()
# 리스트로 큐 구현
queue = []
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
print(queue)
print(queue.pop(0)) # 가장 앞에 있는 놈을 출력해준다.
queue.append(1)
queue.append(4)
print(queue.pop(0))
print(queue)
Deque 덱
⇒ double-ended queue의 약자이다. 양방향으로 추가하고 제거 할 수 있는 자료구조이다. 쉽게 생각하면 stack + queue인 셈!
# 덱
from collections import deque
queue = deque([1, 2, 3, 4])
queue.append(5)
print(queue)
print(queue.popleft())
print(queue)
print(queue.pop())
print(queue)deque는 queue와는 다르게 popleft()라는 메서드가 있다. 덱은 appendleft(x), popleft(x)와 같이 모두 O(1)의 시간 복잡도를 가지기 때문에, list 자료 구조보다 성능이 훨씬 뛰어나다. 무작위 접근의 worst case에서는 O(N)의 성능이 나오는 내부적 연결리스트를 사용함..
Recursion 재귀
DFS와 BFS를 구현하려면 재귀함수도 이해하고 있어야한다.
⇒ 재귀함수에서 알아야하는 가장 중요한 포인트는 재귀를 멈출때의 조건이다. 구조적으로 재귀함수는 스택처럼 작동한다. 예를 들어서 Factorial함수를 보자.
def factorial(n):
if n == 1:
return 1
else:
n *= factorial(n-1)
return n
print(factorial(5))→ 결과 : 120
어떻게 동작을 하는 것인지 생각을 해보면
초기 n = 5일때
n = 5 factorial(4)
n = 4일때
n = 5 4 factorial(3)
n = 5 4 3 factorial(2)
n = 5 4 3 2 factorial(1) → factorial(1) ⇒ 1을 리턴!
재귀를 사용했을 때 얻을 수 있는 장점은 코드가 더 간결해진다.
DFS/깊이 우선 탐색
⇒ 최대한 깊이 내려간 뒤, 더 이상 깊이 내려 갈 곳이 없을 경우 옆으로 이동
- 루트 노드 (혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 미로 찾기의 경우를 예를 들어보면 우리는 막다른 길이 나올때까지 계속 경로를 탐색하다가 막다른 길이 나오면 가장 가까운 갈림길로 돌아가서 다시 다른 방향을 탐색하는게 깊이 우선 탐색 방식과 유사하다.
- 모든 노드를 방문하고자하는 경우에 이 방법을 선택함
- 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.
- 검색 속도 자체는 너비 우선 탐색에 비해서 느리다.
인접 리스트
# 인접리스트 방식
graph = [[] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장
graph[0].append((1, 7))
graph[0].append((2, 5))
# 노드 1에 연결된 노드 정보 저장
graph[1].append((0, 7))
graph[2].append((0, 5))
print(graph)인접 행렬
# 인접 행렬 방식 예시
INF = 999999999
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)인접 행렬에서는 1과 7이 연결되어 있는지 확인 하는데 시간 복잡도가 1인 반면에 인접 리스트에서는 1이나 7에 연결된 노드를 다 탐색하면서 찾아야한다.
인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다.
DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.
탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
2번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.
# 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]
]
visited = [False] * 9
dfs(graph, 5, visited)5번 노드를 먼저 방문 할때를 생각해보자.
스택에 5 저장 → 인접 노드 중에서 가장 작은 3을 스택에 넣는다. → 3에서 아직 방문하지 않은 1 번과 4번 중 1번 선택 후 스택에 넣는다.
→ 2, 8번 중 2번 선택 후 스택에 저장
현재 스택 2 1 3 5 즉 스택에는 내가 방문한 순서대로 들어가 있음!
→ 등등
BFS/너비 우선 탐색
⇒ 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
- 로트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
- 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다. ex) 모든 인스타 그램 계정을 노드 그래프로 표현하고 나와 다른 어떤 한면 사이의 존재하는 경로를 찾는 경우 → 깊이 우선 탐색은 모든 친구 관계를 다 찾아볼 수 있다. 너비 우선 탐색의 경우 나와 가까운 관계부터 탐색한다.
탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
2번 과정을 더이상 수행할 수 없을 때까지 반복한다.
# BFS 구현
from collections import deque
def bfs(graph, v, visited):
visited[v] = True
queue = deque([v])
while queue:
item = queue.popleft()
print(item, end =' ')
for i in graph[item]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[], # 0번 노드 사용 x
[2, 3, 8], # 1
[1, 7], # 2
[1, 4, 5], # 3
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)음료수 얼려 먹기
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분 0, 칸만이가 존재하는 부분은 1로 표시된다. 궁멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
문제 해결 전략
인접해 있는 것 끼리는 1로 취급을 한다.
인접해 있는 것을 판단하는 것은 방향이 위, 아래, 좌, 우가 있다. 그것을 파라미터로 넘겨줘서 방문 표시를 해서 인접한 녀석들 끼리는 계속 재귀적으로(stack) 방문하여 방문 표시를 남기면 분리된 모든 영역의 개수를 구할 수 있다.
# 음료수 얼려먹기
from collections import deque
n, m = map(int, input().split())
data = []
cnt = 0
direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for i in range(n):
data.append(list(map(int, input())))
def dfs(x, y):
if (x < 0) or (x >= n) or (y < 0) or (y >= n):
return 0
if data[x][y] == 0:
print(x, y)
data[x][y] = 1
dfs(x+direction[0][0], y+direction[0][1])
dfs(x+direction[1][0], y+direction[1][1])
dfs(x+direction[2][0], y+direction[2][1])
dfs(x+direction[3][0], y+direction[3][1])
print("---------------------")
return 1
return 0
for i in range(n):
for j in range(m):
if dfs(i, j) == 1:
cnt += 1
print(cnt)
# test_cast
# 000001111000000
# 111111011111100
# 110111011011100
# 110111011000000
# 110111111111111
# 110111111111000
# 110000000111111
# 011111111111111
# 000000000111111
# 011111111100000
# 000111111110000
# 000000011110000
# 111111111111001
# 111000111111111
# 111000111111111미로 탈출
NxM 크기의 직사각형 형태의 미로에 갇혀 있고 입구 (1, 1) 미로의 출구는 (N, M) 의 위치가 출구이다. 한번에 한 칸 씩 이동할 수 있다.
괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시. 동빈이가 탈출하기 위해서 최소 움직여야하는 칸의 개수
문제 해결 전략
앞에 문제와 유사하지만 최단 거리를 찾아야하는 문제이다. 큐에 갈 수 있는 경로를 즉 길인 경우 값이 1인 케이스만 저장하고 그것 들로 부터 더 갈 수 있는 길을 찾아본다. 한번도 가보지 않은 길은 원래 값에서 이전 노드의 길이만 더해서 탐색한다. 즉 방문 표시 및 시작 점서부터 특정 위치의 노드의 거리까지 같이 저장하게 된다.
코드
# 미로 탈출
from collections import deque
n, m = map(int, input().split())
#graph = []
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
# for i in range(n):
# graph.append(list(map(int, input())))
graph = [
[1, 0, 1, 0, 1, 0],
[1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]
]
def bfs(graph, x, y):
queue = deque()
queue.append([x, y])
while queue:
x, y = list(queue.popleft())
print("queue : ", queue)
for dx,dy in direction:
if x+dx >= n or x+dx < 0 or y+dy >= m or y+dy < 0:
continue
if graph[x+dx][y+dy] == 1:
print("*dx, dy: ", x+dx, y+dy)
queue.append([x+dx, y+dy])
graph[x+dx][y+dy] = graph[x][y] + 1
else:
continue
return graph[n-1][m-1]
print(bfs(graph, 0, 0))
print(graph)