깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) +백준 1260 문제풀이🙋‍♂️

DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.

*그래프(graph): 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아놓은 자료구조

*탐색(search): 많은 양의 데이터 중 원하는 데이터를 찾는 과정

 

DFS (Depth-First Search, 깊이 우선 탐색)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 재귀 함수 또는 스택 자료구조를 사용하여 구현

DFS

동작 과정

1. 탐색 시작 노드를 *스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

3. 방문하지 않은 인접 노드가 없으면 스택에처 최상단 노드 꺼내기

4. 더 이상 수행할 수 없을 때 까지 2와 3을 반복

*스택(stack): 값이 위로 쌓이는 구조, 후입 선출(LIFO, last in first out) 방식

 

BFS (Breadth-First Search, 너비 우선 탐색)

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 사용하여 구현

 

BFS

동작 과정

1. 탐색 시작 노드를 *큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 후 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 넣고 방문처리

3. 더 이상 수행할 수 없을 때 까지 2를 반복

*큐(Queue): 값이 아래로 쌓이는 구조, 선입 선출(FIFO, First in first out) 방식

 

DFS와 BFS의 비교

DFS와 BFS 비교

	DFS	BFS
저장공간	수요 적음 (현재 경로상의 노드만 기억하면 됨)	수요 많음 (다음에 탐색할 노드들을 저장해야 함)
구현 난이도	비교적 간단함	비교적 어려움
검색 속도	비교적 느림	비교적 빠름
최단 경로	보장되지 않음 (해를 구하면 탐색 종료)	보장됨 (너비 우선 탐색)

 

DFS와 BFS 문제풀이

🐍백준 1260번: DFS와 BFS

 

문제 풀이

import sys
sys.stdin = open("input.txt","r")   #입력 예시 담긴 input.txt 가져오기

from collections import deque

n, m, v = map(int, input().split())

#숫자들의 연결 확인을 위해 행렬 리스트 생성
#정점의 번호(1부터 시작)와 리스트의 인덱스를 맞추기 위해 n+1 X n+1
graph = [[0] * (n + 1) for _ in range(n + 1)] 

for i in range(m):  #간선의 개수만큼 반복
    a,b = map(int,input().split())  #간선이 연결하는 두 노드 번호 a,b
    graph[a][b]=graph[b][a]=1   #연결된 경우 1입력(간선은 양방향) 

def dfs(start, visited):    #깊이 우선 탐색 dfs(시작노드, 방문 처리)
    visited += [start]  #시작 노드 방문 처리
    for c in range(len(graph[start])):
        if graph[start][c] == 1 and (c not in visited):
            dfs(c, visited)
    return visited  

def bfs(start): #너비 우선 탐색 bfs(시작노드)
    visited = [start]   #방문 처리
    queue = deque()
    queue.append(start) #시작 노드 큐에 삽입

    while queue:    #큐에 남은것이 없을 때 까지 반복
        v = queue.popleft() #큐에서 노드 꺼내기
        for c in range(len(graph[start])):
            if graph[v][c] == 1 and (c not in visited):
                queue.append(c) #방문하지 않은 노드를 큐에 넣고
                visited.append(c)   #방문처리
    return visited

print(*dfs(v,[]))
print(*bfs(v))

 

그래프를 구현하는 방식에는 인접 행렬과 인접 리스트 방식이 있는데 이 문제에서는 인접행렬 방식으로 구현했다.

 

인접 행렬은 그래프의 정점(노드라고도 함) 2차원 배열로 만든다.

간선에 의해 연결된 정점(인접 정점, adjacent vertex)는 1, 아니면 0의 값을 가진다.

 

DFS의 경우 재귀함수로, BFS의 경우 큐로 구현했다.

 

---

참고 영상

👍👍👍

참고 자료

[Algorithm] DFS 알고리즘 (Depth First Search)

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

 

1260번: DFS와 BFS