DFS/BFS - 그래프 탐색 알고리즘
스택 자료구조 - 선입후출, 입구와 출구가 동일한 형태, 박스 쌓고 내린다고 생각하면 됨
-> 삽입하고 삭제하는 방식
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[::-1]) #최상단 원소부터 출력
print(stack[::]) #최하단 원소부터 출력큐 자료구조 - 선입선출, 입구와 출구가 모두 있는 터널, 은행 대기표/편의점 우유 생각하면 됨
리스트로 구현은 가능한데 시각복잡도가 높아서 비효율적이라 덱 라이브러리를 꼭 사용
from collections import 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) #먼저 들어온 순서대로 출력
queue.reverse() #역순으로 바꾸기
print(queue) #나중에 들어온 원소부터 출력
재귀 함수 - DFS 에서 자주 사용, 파이썬에서 최대 재귀 깊이 제한이 있어서 오류 메세지가 나올 수 있음
종료 조건 : 100번째 호출을 했을 때 종료되도록 종료 조건 명시
-모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.(유리할 때도 있고 불리할 때도 있음)
-컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓여서 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다.
def recursive_function(i):
if i == 100:
return
print(i, '번째 재귀함수에서', i+1,'번째 재귀함수를 호출합니다')
recursive_function(i+1)
print(i,'번째 재귀함수를 종료합니다.')
recursive_function(1)
재귀 함수 예제1 - 팩토리얼 예제, 0! = 1
def factorial_recursive(n):
if n <= 1: #n이 1이하인 경우 1을 반환
return 1
#n! = n*(n-1)!
return n*factorial_recursive(n-1)
print(factorial_recursive(5))
재귀 함수 예제2 - 유클리드 호제법(최대공약수 계산)
def gcd(a,b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192,162))
DFS 알고리즘 - 깊이 우선 탐색, 스택 자료구조(or 재귀 함수)
- 탐색 시작 노드를 스택에 삽입하고 방문 처리함
- 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 더이상 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)
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[],#인덱스 0은 비워둠
[2,3,8], #1번 노드와 연결되어 있는거
[1,7],#2번 노드와 연결되어 있는거
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
# False 넣어서 모든 노드를 아직 하나도 방문하지 않은 것처럼 초기화
visited = [False]*9
# 1-8번 노드를 갖고 있어서 인덱스0은 사용하지 않는 방식으로 한 개 더 크게 9
dfs(graph, 1, visited)BFS 알고리즘 - 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색, 큐 자료 구조
- 탐색 시작 노드를 큐에 삽입하고 방문 처리함
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
from collections import deque
#BFS 메서드 정의
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 = [
[],#인덱스 0은 비워둠
[2,3,8], #1번 노드와 연결되어 있는거
[1,7],#2번 노드와 연결되어 있는거
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
bfs(graph,1,visited)
문제1. 음료수 얼려먹기 (DFS or BFS, 그래프 형태로 모델링할 수 있으므로)
n,m = map(int,input().split())
#그래프 생성
graph = []
for i in range(n):
graph.append(list(map(int,input())))
#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
#모든 노드에 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
result += 1
print(result)
문제2. 미로 탈출 - BFS
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]
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]
print(bfs(0,0))
❄️