DFS (Depth First) : 루트부터 시작해서 한 브랜치의 자식 노드를 모두 파악한 뒤 다음 브랜치로 넘어가며 탐색
DFS의 예시 - 미로탐색에서 한 길을 쭉 본다음 길이 없으면 그다음 갈림길로 돌아와서 다시 쭉 탐색하는 방식. BFS보다 간단하며 BFS보다 느리다. 모든 노드를 탐색하고자 할 때 사용한다.
DFS 구현 - 스택과 재귀함수로 구현한다.
BFS (Breadth First) : 루트부터 시작해서 각 브랜치의 level 별로 인접한 노드를 먼저 탐색
BFS 예시 - 두 노드 사이의 최단 경로를 찾을 때 사용. DFS보다 복잡하지만 빠르다.
BFS 구현 - 큐로 구현한다.
어떤 문제에서 사용해야 할까?
1. 그래프의 모든 정점을 방문해야 하는 문제 > 둘 다 가능.
2. 경로의 특징을 저장-활용해야 하는 문제, 제약조건이 있는 문제 ex) 경로에서 노드의 값이 중복되는 값이 있으면 안된다~ 등. > DFS 사용
3. 최단거리 구해야 하는 문제 > BFS 사용. 현재 노드에서 가까운 곳부터 (값이 작은 곳부터) 찾기에 그게 최솟값이다.
백준 1260 파이썬 풀이
첫번째 입력은 정점, 간선, 시작 번호이다.
각 변수 N, M, V로 인풋을 받아주자.
그다음 M개의 인풋은 정점 간 간선을 의미한다.
이를 표현하기 위해 2차원 NxN zero metric으로 그래프를 표현하고, 각 인풋에 해당하는 좌표를 1로 만들어줌으로써 간선이 연결됨을 표기한다.
그 뒤, dfs와 bfs를 위한 방문 리스트를 만들어준다.
N,M,V = map(int,input().split())
# zero metric
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
a,b = map(int,input().split())
graph[a][b] = graph[b][a] = 1
# visited list
visited1 = [0]*(N+1)
visited2 = [0]*(N+1)
dfs를 만든다.
함수 실행 시 visited에 값을 넣고, 재귀를 통해 탐색할 수 있도록 한다.
이때 loop와 조건문으로 간선이 있고, 방문한 적이 없는 정점을 찾는다.
def dfs(V):
visited1[V] = 1
print(V, end=' ')
for i in range(1, N+1):
if graph[V][i] == 1 and visited1[i] == 0:
dfs(i)
bfs는 큐로 만들 수 있다. while queue:를 통해 queue가 빌 때 까지 탐색을 수행한다.
def bfs(V):
queue = [V]
visited2[V] = 1 #방문처리
while queue:
V = queue.pop(0) #방문 노드 제거
print(V, end = ' ')
for i in range(1, N+1):
if(graph[V][i] == 1 and visited2[i] == 0):
queue.append(i)
visited2[i] = 1 # 방문처리dfs(V)
print()
bfs(V)
