DFS
- 깊이 우선 탐색 알고리즘으로 그래프에서 깊은 노드를 우선적으로 탐색하는 알고리즘
- 스택 자료구조 또는 재귀함수를 이용
- 동작 과정
- 탐색 시작 노드를 스택에 삽입 후 방문처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
※ 보통 번호가 낮은 인접노드부터 방문
- 노드의 탐색순서(스택에 들어간 순서)
def dfs(graph), v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[], # 0번노드 : 존재하지 않음. 인덱스와 1번부터 시작하는 그래프 노드의 key를 맞추기 위함.
[2, 3, 8], # 1번노드 : 인접노드는 2,3,8 노드
[1,7], # 2번노드 : 인접노드는 1,7 노드
[1,4,5], # 3번노드 : ...
[3,5], # 4번노드 : ...
[3,4],
[7],
[2,6,8],
[1,7], # 8번노드 : ...
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)DFS2
- 아래와 같은 입출력으로 데이터를 받으면 DFS 알고리즘은 어떻게 달라져야할까?
입출력예시
#입력
4 5 1
1 2
1 3
1 4
2 4
3 4
# 출력
1 2 4 3코드
n, m, v = map(int, input().split(" "))
matrix = [[0] * (n+1) for _ in range(n+1)] # n + 1 하는 이유 : 0번 인덱스부터 하면 헷갈리니까 맞추려고
visited = [0] * (n+1)
for i in range(1, m+1):
frm, to = map(int, input().split(" "))
matrix[frm][to] = matrix[to][frm] = 1
def dfs(graph, visited, v):
if visited[v] == 0:
visited[v] = 1
print(v, end = " ")
for i in range(1, n+1):
if graph[v][i] == 1 and visited[i] == 0:
dfs(graph, visited, i)
dfs(matrix, visited, v)
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 not visited[i]:
queue.append(i) # 현재 노드 큐에 삽입
visited = True # 현재 노드 방문 처리
graph = [
[], # 0번노드 : 존재하지 않음. 인덱스와 1번부터 시작하는 그래프 노드의 key를 맞추기 위함.
[2, 3, 8], # 1번노드 : 인접노드는 2,3,8 노드
[1,7], # 2번노드 : 인접노드는 1,7 노드
[1,4,5], # 3번노드 : ...
[3,5], # 4번노드 : ...
[3,4],
[7],
[2,6,8],
[1,7], # 8번노드 : ...
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 bfs 함수 호출
bfs(graph, 1, visited)BFS2
- 아래와 같은 입출력으로 데이터를 받으면 BFS 알고리즘은 어떻게 달라져야할까?
입출력예시
#입력
4 5 1
1 2
1 3
1 4
2 4
3 4
# 출력
1 2 3 4코드
from collections import deque
n, m, v = map(int, input().split(" "))
matrix = [[0] * (n+1) for _ in range(n+1)] # n + 1 하는 이유 : 0번 인덱스부터 하면 헷갈리니까 맞추려고
visited = [0] * (n+1)
for i in range(1, m+1):
frm, to = map(int, input().split(" "))
matrix[frm][to] = matrix[to][frm] = 1
def bfs(matrix, v, visited):
q = deque()
if visited[v] == 0:
visited[v] = 1
q.append(v)
while q:
cur = q.popleft()
print(cur, end = " ")
for i in range(len(visited)):
if matrix[cur][i] == 1 and visited[i] == 0:
visited[i] = 1
q.append(i)
bfs(matrix, 1, visited)
yozzum