### 그래프 탐색 알고리즘 : DFS/BFS
이 그래프 탐색알고리즘 DFS와BFS를 해결하기 위해서 알고 있어야할 자료구조가 있다.
우선
스택
자료구조이다.
python에서 스택 자료구조는 리스트를 활용해서 구현한다.
append,pop
append() : 리스트에 요소를 추가하다
pop() : 리스트의 오른쪽 끝부분을 삭제한다
이 둘을 사용해서 스택을 구현하면된다 !!
스택이 나오면 스택 친구가 무조건 다음에 나온다 !
바로 큐이다
큐
큐 자료구조이다.
python에서 큐 자료구조는 deque을 이용해서 사용하는 경우가 많다.
물론, 리스트를 활용해서 구현해도 되지만 그 보다는 deque을 collections에서 불러와서 사용하면 시간복잡도가 더 낮게 나온다.
collections 내장 라이브러리를 C언어로 구현해서 그렇다나뭐라나...
append,popleft
popleft : 리스트의 제일 왼쪽을 삭제한다.
재귀함수
Python 최대 재귀 깊이..
1000까지이기에
DFS를 사용할 경우
import sys
limit = 15000
sys.setrecursionlimit(limit)이를 가져와서 재귀 깊이제한을 제어할 수 있다.
유클리드 호제법
재귀함수 예제로 유명한 유클리드 호제법이다.def gcd(a,b): if a%b==0: return b else : return gcd(b,a%b) print(gcd(192,162))이와 같이 최대공약수를 편하게 구할 수 있다.
(math.gcd 해도 되는데 헤헷)
재귀함수 유의사항
그럼 이제 DFS/BFS를 위한 모든 준비는 끝났다
DFS(Depth-Frist-Search)
깊이 우선 탐색의 탐색 순서는 아래와같다.
그냥 .. 깊게 먼저들어간다고 생각하면 간단하다.
def dfs(graph,v,visted):
visted[v]=True
print(v,end=" ")
for i in graph[v]:
if not visted[i]:
dfs(graph,i,visted)
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4]
[7],
[2,6,8],
[1,7]
]
visted=[False]*9
dfs(graph,1,visted)
보통 그래프는 입력받는 케이스가 많지만 우리가 위에 본 그래프는 저렇게 생겼다고 보면 된다..!
코드 설명은 간단하다.
그냥 ... 방문하지 않았던 곳은 visted라는 리스트 안에 False라고 두고 방문할때마다 True로 바꿔주는것이다.
그런데 dfs를 재귀를 통해 쭉쭉 깊은곳을 탐색해나가는 것이다.
DFS 예제
음료수 얼려 먹기
간단히 문제 해결전략만 생각해보면
칸들을 돌면서 0을 1로바꿔주면서 블럭들을 확인해나가며 cnt를 올려주면 될것같은 문제이다.해결아이디어
영상에서 제시한 해결 아이디어는 이렇다.답
def dfs(x,y): if x<=-1 or x>=n or y<=-1 or y>=m: return False if graph[x][y]==0: #0 인근 0 노드 1로 변경 graph[x][y]=1 dfs(x-1,y) dfs(x+1,y) dfs(x,y-1) 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()))) cnt = 0 for i in range(n): for j in range(m): if dfs(n,m)==True: cnt+=1 print(cnt)
BFS : Breath-First Search
너비 우선 탐색의 탐색순서는 아래와 같다.
그냥.. level별로 탐색한다고 보면될거같다.
너비부터,.,?
깊은곳부터 탐색하는 것이 아니라!!
이를 구현한 코드는 아래와 같다.
#BFS
from collections import deque
def bfs(graph,start,visted):
queue = deque([start])
visted[start]=True
while queue:
v = queue.popleft()
print(v,end=" ")
for i in graph[v]:
if not visted[i]:
queue.append(i)
visted[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)이것도 이론적인 BFS 코드이지 문제에서는 좀 다르게 활용되지만 이 틀에서 벗어나지 않는것같다.
BFS 예제
미로탈출
이는 BFS로 1이 들어있는 칸을 이동할때마다 이동횟수로 바꿔주면서 제일 먼저 원하는 위치에 도착했을때의 횟수를 출력해주면 되는 문제일것같다.
영상에서의 문제해결아이디어는 아래와 같이 제시한다.
문제 해결 아이디어
뭐.. !
나의 생각과 비슷한거같다 !
답
from collections import deque
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):
cx = x + dx[i]
cy = y + dy[i]
if cx<0 or cx>=n or cy<0 or cy>=m or graph[cx][cy]==0:
continue
if graph[cx][cy] ==1:
graph[cx][cy]=graph[x][y]+1
queue.append((cx,cy))
return graph[n-1][m-1]
n,m = map(int,input().split())
graph = []
for i in range(n):
graph.append(list(map(int,input())))
print(bfs(0,0))이로서 DFS,BFS 관련 학습을 끝냈다.
참고 강의 : DFS&BFS
