[TIL] 05/20 항해99 12일차 - BFS, DFS vs BFS, 문제풀이

 

들어가며

알고리즘 2주차의 1일차... 오늘의 회고는 짤 하나로 요약하고, 지난 그래프 알고리즘 DFS에 이어 BFS에 대해 TIL을 작성하고자 한다

 

알고리즘 2주차의 1일차 요약

 

---

그래프 탐색(순회)

깊이 우선 탐색(BFS, Breadth First Search)

 

BFS는 특정 노드에서 시작해 인접한 노드를 먼저 탐색해나가는 방법으로, 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 쉽게 말하면, 그림처럼 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 방식으로 그래프를 순회하는 방법이다.

 

BFS는 일반적으로 큐를 이용해서 지금 위치에서 갈 수 있는 곳들을 모두 큐에 넣는 방식으로 구현한다.

 

 

역시나 BFS도 예시를 들어가며 자세하게 설명해주는 글이 있어 첨부한다.

 

[알고리즘] 너비 우선 탐색(Breadth First Search : BFS) 이란?

[알고리즘] 너비 우선 탐색(Breadth First Search : BFS) 이란?

 

 

BFS 구현하기

BFS의 구체적인 동작방식은 다음과 같다

 

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
• 2번째 과정을 더 이상 수행할 수 없을 때까지 반복한다

 

from collections import deque

def bfs(graph, start, visited):

		# 시작점을 담아준다.
		queue = deque([start])

		# 방문 처리를 해준다.
		visited[start] = True

		# queue가 존재할 때까지 인접한 노드들을 탐색한다. 
		while queue:
			
			# 시작점을 가져온다
			v = queue.popleft()
			
			# 순서를 확인하기 위해 print
			print(v, end=' ')

			# 시작점과 인접해있는 노드들을 탐색한다.
			for i in graph[v]:
				# 인접해 있는 노드들을 방문한 적이 있는 지 확인한다.
				# 방문한 적이 없다면 queue에 담아주고 방문 처리를 해준다.
				if not visited[i]:
					queue.append(i)
					visited[i] = True

 

기본적으로 구현에서 DFS와 크게 다르지 않다. DFS는 스택을, BFS는 큐를 사용한다는 점이 다르다.

 

 

 

테스트용 코드

graph = [
    [],
    [2, 3, 8],
    [7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

 

 

DFS(깊이 우선 탐색) vs BFS(너비 우선 탐색)

출처 https://namu.wiki/w/BFS

 

지금까지 DFS와 BFS에 대해서 공부해보았다. 그런데 대체 어떤 문제에 DFS를 쓰고 어떤 문제에 BFS를 써야할까?

DFS와 BFS의 장단점과 어느 문제에 어느 알고리즘을 적용하는게 적절한지 구글링한 결과들을 한번 정리해보자.

 

 

DFS

장점

• BFS에 비해 저장공간의 필요성이 적다. 백트래킹을 해야하는 노드들만 저장해주면 된다.
• 찾아야하는 노드가 깊은 단계에 있을 수록, 그 노드가 좌측에 있을 수록 BFS보다 유리하다.

 

단점

• 답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠질 우려가 있다.
• 찾은 값이 최단 경로라는 보장이 없다.

 

DFS로 풀었을 때, 유리한 상황

• 이동할 때마다 가중치가 붙거나 이동 과정에서 여러 제약이 있을 경우 DFS로 접근하면 탐색 시간은 더 걸리지만, 가중치에 대한 변수를 지속해서 관리할 수 있다는 장점이 있어서 코드 구현에 더 편리하다.
• 모든 노드를 방문해야할 때나 재귀적으로 계속 호출해야하는 문제일 경우
  예) 모든 경우의 수
• 경로의 특징을 저장해둬야 하는 문제일 경우
  예) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등

 

BFS

장점

• 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장한다.
• 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.
• 노드 수가 적고 깊이가 얕은 값이 존재 할 때 유리하다.

 

단점

• 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하는데, 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공간 필요하다.
• 노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적이다.

 

BFS로 풀었을 때, 유리한 상황

• 현재 나의 위치에서 가장 가까운 노드를 먼저 방문하는 알고리즘
• 최단거리(최소 횟수)를 찾는 문제와 임의의 경로를 찾는 문제
  예) 미로 탐색 문제
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않은 경우

 

 

문제풀이

[leetcode] 200. 섬의 개수 (Number of Islands)

[leetcode] 200. 섬의 개수 (Number of Islands)

여러번 구현 연습을 하자!

 

 

---

마치며

알고리즘 난이도가 올라감에 따라 차라리 개념 공부를 열심히 해야겠다는 생각이 들어 많은 자료를 찾아보고 최대한 자세히 쓰려고 노력하고 있다. 이번 REST API 발표때 처럼 이 글들이 유용하게 쓰이길 바랄 뿐이다.

 

+

추가로 알고리즘을 공부하면서 여러가지 궁금증이 생겨 구글링을 하던 중에 몇가지 좋은 글들이 보여 첨부해본다. 

 

내가 정리하는 코딩테스트 문제 유형 별 풀이 방법

내가 정리하는 코딩테스트 문제 유형 별 풀이 방법

 

최단거리 문제 알고리즘에 대한 궁금증 정리

최단거리 문제 알고리즘에 대한 궁금증 정리

 

 

++

알고리즘 공부가 재미없다고 징징댔더니 항해99 수강생 재호님이 보내준 사진

 

---

출처

 

DFS, BFS의 설명, 차이점

 

DFS/BFS 문제 판단 기준

 

DFS vs BFS