[이.코.테] DFS/BFS

 

 

 

 

대표 문제 유형

1. 경로탐색 유형 (최단거리, 시간)

2. 네트워크 유형 (연결)

3. 조합 유형 (모든 조합 만들기)

 

	DFS	BFS
알고리즘 검증	동작 검증을 하기 쉬움	어려움
	코드 간결, 버그 발생할 가능성 적음
수행 시간	복불복	대박날 확률도 적지만 쪽박 찰 확율도 적다
= 시간 복잡도	높다	낮다
문제 난이도	쉬운 문제일 경우 추천	난이도 있어보이거나 DFS로 풀기 오래걸릴 것 같은 경우 추천

 

 

=> 한 문제를 두 방식으로 풀어보며 익혀두기

 

백준 연습 문제

1260 -- DFS와 BFS : 그래프에서 DFS / BFS 연습

2606 -- 바이러스 : 그래프에서 DFS 활용 연습

2667 -- 단지번호붙이기 : DFS를 이용한 Flood Fill 연습

2178 -- 미로탐색 : BFS로 4방향 탐색 연습

7569 -- 토마토 : BFS로 6방향 탐색 연습

 

 

 

1. DFS (Depth-First Search)

- 깊이 우선 탐색

 

- 스택 방식으로 재귀 함수 이용 (한 놈만 끝까지 패는 유형)

-- 재귀를 계속 타다가 탈출 조건에 먼저 도달하고, 그 다음에 파라미터를 하나씩 바꿔 가면서 정답을 찾는 방식

-- 재귀 깊이가 지나치게 깊어지면 메모리 비용을 예측하기 어렵다.

=> 데이터 사이즈가 일정 이상이면 비추천.

 

- 모든 노드를 방문하고자 할 때 사용

--- 조합을 만들고 정답과 비교

=> 최단 경로를 알 수 없다.

 

- BFS (Breadth-First Search) 너비우선 탐색보다 간단하지만 단순 검색 속도 자체는 느리다.

 

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

2-1. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 넣고 방문 처리,
2-2. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄
(인접노드 방문순서는 문제에서 주어진 조건으로. 없다면 관행적으로 번호가 낮은 순서부터 처리)

3. 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)


# 각 노드의 연결정보 (2차원 리스트)
graph = [
	[],			# 인덱스가 1부터 시작하기 때문에 [0]에 빈 리스트 삽입
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 방문 정보 (1차원 리스트)
visited = [False] * 9	# 인덱스 0을 사용하지 않기 위해 +1

dfs(graph, 1, visited)

 

 

 

2. BFS (Breadth-First Search)

- 너비 우선 탐색: 가까운 노드부터 탐색 

 

- 큐 자료구조 사용 (여러 놈을 한대씩 때리면서 가는 유형)

-- 가장 먼저 넣은 것을 꺼내서 연결된 점을 큐에 넣는 방식으로 진행. 

--- 순서가 보장되어야 하기 때문에 큐 사용

 

- 시간/공간 복잡도 면에서 안정적.

 

- 최단 거리를 구하는 목적으로 사용할 수 있음.

-- 간선의 비용이 모두 같을 경우

--- 각각 다를 경우, 다익스트라 알고리즘 등의 최단거리 알고리즘을 활용해야 한다.

 

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

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

3. 2번 과정을 더이상 수행할 수 없을 때까지 (큐가 완전히 빌 때까지) 반복
3-1. 꺼낸 노드가 목표 지점이면 루프 종료
3-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[i] = True
      
      
# 각 노드의 연결정보 (2차원 리스트)
graph = [
	[],			# 인덱스가 1부터 시작하기 때문에 [0]에 빈 리스트 삽입
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 방문 정보 (1차원 리스트)
visited = [False] * 9	# 인덱스 0을 사용하지 않기 위해 +1

bfs(graph, 1, visited)

 

 

 

 

 

 

깊이 우선 탐색(DFS)

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

https://www.youtube.com/watch?v=BsYbdUnKZ-Y

https://www.youtube.com/watch?v=By77aC9Oe3Q