[알고리즘] DFS & BFS

ryun·2023년 3월 30일
0

알고리즘

목록 보기
2/2

깊이 우선 탐색

재귀 구현 (비교적 간단)

def recursive_dfs(v, discovered=[]):
	dicovered.append(v)
    for w in graph[v]:
    	if w not in discovered:
        	discovered = recursive_dfs(w, discovered)
    return discovered

스택을 이용한 반복 구조로 구현

  • 직관적이라 이해가 쉽다
  • 실행 속도 더 빠르다
def iterative_dfs(start_v):
	discovered = []
    stack = [start_v]
    while stack:
    	v = stack.pop()
    if v not in discovered:
    	discovered.append(v)
        for w in graph[v]:
        	stack.append(w)
return discovered

너비 우선 탐색

  • 다익스트라 알고리즘 등에 유용하게 사용된다
  • BFS는 재귀로 동작하지 않고, 큐를 이용한 반복 구현만 가능하다

큐를 이용한 반복 구조

def iterative_bfs(start_v):
	discovered = [start_v]
    queue = [start_v]
    while queue:
    	v = queue.pop(0)
        for w in graph[v]:
        	if w not in discovered:
            	discovered.append(w)
                queue.append(w)
    return discovered

문제

백준 DFS와 BFS

def dfs(v):
    dfs_check[v] = True
    print(v, end=' ')

    # 모든 요소를 돌면서
    for i in range(1, N + 1):
        # 방문하지 않았고 현재 정점과 연결되어 있는 정점
        if not dfs_check[i] and graph[v][i] == 1:
            dfs(i)

def bfs(v):
    # 큐 생성
    q = [v]
    # 현재 노드 방문 처리
    bfs_check[v] = True
    # 큐가 빌때까지 반복
    while q:
        # 큐에서 하나의 원소를 뽑아 추력
        ci = q.pop(0)
        print(ci, end=' ')
        # 모든 정점을 돌면서
        for i in range(1, N + 1):
            # 해당 원소와 연결되고 아직 방문하지 않은 원소들을 큐에 삽입
            if not bfs_check[i] and graph[ci][i] == 1:
                q.append(i)
                bfs_check[i] = True

# 정점 개수 N, 간선 개수 M, 시작 정점 번호 V
N, M, V = map(int, input().split())
node = {}
dfs_check = [False for _ in range(N + 1)]
bfs_check = [False for _ in range(N + 1)]
graph = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    n, v = map(int, input().split())
    graph[n][v] = graph[v][n] = 1

dfs(V)
print()
bfs(V)

0개의 댓글