🔸 DFS와 BFS는 대표적인 그래프 탐색 알고리즘
🔸 탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
📌 0. 자료구조
Stack
🔸 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
🔸 입구와 출구가 동일한 형태 ex. 박스쌓기
🔸 list 사용
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)Queue
🔸 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)
🔸 입구와 출구가 모두 뚫려있는 형태 ex.터널
🔸 deque 사용
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)재귀함수(Recursive function)
: 자기 자신을 다시 호출하는 함수
🔸 stack 자료구조에 함수가 쌓여 메모리에 올라감
🔸 while이나 for문을 이용하지 않고도 반복적으로 함수 진행 가능
🔸 재귀함수를 문제 풀이에 사용할 때는 재귀 함수의 종료조건을 반드시 명시해야하며, 그렇지 않을 경우 함수가 무한히 호출될 수 있음
=> 재귀함수 시작 부분에 종료조건 명시 => return
🔸 이론적으로 재귀 함수는 반복문을 이용한 모든 코드 구현 가능
🔸 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음
🔸 스택을 사용해야할 때 구현상 스택 라이브러리 대신 재귀함수를 이용하는 경우 많음 => DFS를 간결하게 작성하기 위해 재귀함수 사용
🔸ex1.
def recursive_function(i):
if i == 0:
return
print(i,"번째 재귀함수에서", i+1, "번째 재귀함수를 호출합니다.")
recursive_function(i+1)
print(i, "번째 재귀함수를 종료합니다.")
recursive_function(1)🔸 ex2.
def factorial_recursive(n):
if n<=1:
return 1
return n*factorial_recursive(n-1)🔸 ex3. 최대공약수 계산(유클리드 호제법)
🔹 두 자연수 A와 B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다
def GCD(A,B):
if (A%B == 0):
return B
else:
return GCD(B,A%B)
print(GCD(192,162))📌 1. DFS (Depth-First Search)
1. DFS
🔸 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
🔸 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작은 다음과 같다
1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3) 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
2. 동작예시
🔸 기본 방문 기준: 번호가 낮은 인접 노드부터 방문
def dfs(graph, v, visited):
#현재 노드 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if visited[i] == False:
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,1,visited)
📌 2. BFS (Breadth-First Search)
1. bfs
🔸 BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
🔸 Queue 자료구조를 사용하며 구체적인 동작은 다음과 같다.
1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
🔸 특정 조건에서 최단 경로 문제 해결에 유리
💡 DFS는 스택에 방문하지 않은 노드를 하나씩 넣는데, BFS는 큐에 방문하지 않은 노드를 한 번에 넣음
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 visited[i] == False:
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]]
visited = [False]*9
bfs(graph, 1, visited)ex
ex1. 음료수 얼려먹기
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,y-1)
dfs(x+1,y)
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):
if dfs(i,j)==True:
result += 1
print(result)
print(graph)ex2. 미로탈출
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))