많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 i.e) DFS/BFS
First In Last Out
Last In First Out
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) # [5, 2 ,3,1]
print(stack[::-1]) #[1, 3, 2, 5]
append(), pop()
append() 메소드는 리스트의 가장 뒤쪽에 데이터 삽입
pop() 메소드는 리스트의 가장 뒤쪽에 데이터 제거
First In First Out
from collections import deque
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) #먼저 들어온 순서대로 출력, [3,7,1,4]
queue.reverse()
print(queue) # 나중에 들어온 순서대로 출력 [4,1,7,3]
내부적으로 스택 자료구조와 동일 i.e) DFS
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
#재귀적으로 구현한 n!
def factorial_recursive(n):
if n <=1:
return 1
return n * factorial_recursive(n-1)
# n * (n-1) * ... 1
⭐️ 스택 자료구조 이용
Depth-First Search(깊이우선탐색)
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
DFS의 기능을 생각하면 순서와 상관없이 처리해도 되지만, 코딩 테스트에서는 번호가 낮은 순서부터 처리하도록 명시하는 경우가 있음 -> 번호가 낮은 순서부터 구현하기
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리 -> 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 제거
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 잓ㅇ
INF = 99999999999 #
graph = [
[0,7,5],
[7,0,INF],
[5,INF,0]
]
특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적음
#행(row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [ [] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))
print(graph)
#[[(1,7), (2,5)], [(0,7)], [(0,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)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],# 시작 지점은 비워두기
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 처음 노드 1 -> graph[1] = [2,3,8], 제일 작은 노드 2 방문 ->
#graph[2] = [1,7], 1은 방문 했으니 노드 7 방문 -> ...
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 # 기본값 false , 인덱스 0 을 사용하지 않기 위해 노드 + 1
#함수 호출
dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5
⭐️ 큐 사용
DFS 보다 구현이 조금 더 빠름
Breadth First Search(너비 우선 탐색)
가까운 노드부터 탐색하는 알고리즘
1.탐색 시작 노드를 큐에 삽입하고 방문 처리
2.큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3.2번의 과정을 더 이상 수행할 수 없을 때까지 반복
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
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],# 시작 지점은 비워두기
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 처음 노드 1 제거-> graph[1] = [2,3,8], 모두 방문 (근접 기준) ->
#graph[2] = [1,7], 1은 방문 했으니 노드 7 방문 ->
#graph[3] = [1,4,5], 1은 방문했으니 4,5 방문 -> ...
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 # 기본값 false , 인덱스 0 을 사용하지 않기 위해 노드 + 1
#함수 호출
bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6
왼쪽에 값을 입력할 때 appendleft()
오른쪽에 값을 입력할 때 append()
왼쪽에서 값을 빼고 싶다면 popleft()
DFS로 하나의 깊이 우선 탐색이 끝나면 카운트
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
#dfs로 특정한 노드를 방문한 뒤에 연결된 모든 노드 방문
def dfs(x,y):
# 주어진 범위 벗어나면 종료
if x >=n or x <= -1 or y >=m or y <= -1:
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
#모든 노드에 대해서 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
result += 1
print(result)
# N, M을 공백으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
ice_board = []
for i in range(n):
ice_board.append(list(map(int, input())))
# 상하좌우 진행용 방향 리스트
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 아이스크림 개수
count = 0
# dfs를 통해 현재 노드를 방문한 뒤, 연결된 모든 노드들을 방문
def dfs(start_x, start_y):
# 현재 노드를 방문 처리
ice_board[start_x][start_y] = 1
# 현재 노드와 인접한 모든 노드들을 탐색하며, 방문 가능할 경우 방문
for i in range(4):
# 인접 노드 좌표
nx = start_x + dx[i]
ny = start_y + dy[i]
# 인접 노드가 얼음판 내부에 위치할 경우
if (nx >= 0 and nx < n and ny >= 0 and ny < m):
# 인접 노드에 음료수를 채울 수 있는지 확인
if (ice_board[nx][ny] == 0):
# 인접 노드 방문
dfs(nx, ny)
# 모든 위치에 음료수 채우기
for i in range(n):
for j in range(m):
# 해당 노드에 음료수를 채울 수 있다면
if (ice_board[i][j] == 0):
# 해당 노드에서 dfs 탐색 시작
dfs(i,j)
count += 1
print(count)