[Algorithm] DFS / BFS
수업 시간에 배운 DFS와 BFS에 대해 다시 한번 정리해보았습니다.
이론상으로는 정리가 되지만 알고리즘 적용이 어려워 이를 중점으로 내용을 채워나가려합니다 :)
그래프(Graph)
그래프는 노드와 그 노드를 연결하는 간선으로 이루어진 비선형 데이터 구조
1
2
3
4
5
"선형 구조" ? 원소들을 하나씩 순차적으로 나열시킨 형태
(ex) 스택, 큐
"비선형 구조" ? 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태
(ex) 트리, 그래프
그래프를 탐색하는 방법
- 깊이 우선 탐색 (DFS)
- 너비 우선 탐색 (BFS)
DFS (Depth-First Search)
최대한 깊이 내려간 뒤, 더 이상 갈 곳이 없을 경우 옆으로 이동 
예시
미로 찾기 -> 한 방향으로 가다 길이 막히면 가장 가까운 갈림길에서 다시 탐색
- 모든 노드를 방문하고자 하는 경우
- DFS가 BFS에 비해 간단
- DFS가 BFS에 비해 검색 속도 느림
동작 과정
⭐️ Stack 또는 재귀함수로 구현된다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리한다.
- 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 즉, 매번 최상단 원소를 기준으로 방문하지 않은 인접 노드가 있으면 그 노드로 방문을 수행하는 것이다.
- 더 이상 2번 과정을 할 수 없을 때까지 반복한다.
BFS (Breadth-First Search)
최대한 넓게 이동(인접 노드 먼저 탐색)한 다음, 더 이상 갈 곳이 없을 경우 아래로 이동 
예시
1
2
예은과 민지 사이에 존재하는 경로
-> 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 예은과 민지 사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색 경우 : 모든 친구 관계를 다 탐색
- 너비 우선 탐색 경우 : 예은과 가까운 관계부터 탐색
즉,
두 노드 사이의 최단 경로를 찾고 싶은 경우 BFS 사용
1
2
3
4
BFS로 효과적으로 풀 수 있는 문제의 3가지 조건
1. 최소 비용 문제
2. 간선의 가중치가 1이다.
3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.)
동작 과정
⭐️ Queue로 구현
- 탐색 시작 노드를 큐에 삽입하고, 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- DFS를 수행할 때에는 인접하지 않은 노드에 대해 다시 한번 스택에 넣으면서 수행하였지만, BFS는 해당 시점에서 인접한 노드를 한 번에 전부 큐에 넣는다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
DFS와 BFS의 시간 복잡도
두 방법 모두 모든 노드를 탐색하므로 시간 복잡도는 동일하다. 인접 리스트 사용 -> O(N+E)
인접 행렬 사용 -> O(N²)
여기서 N은 노드의 수, E는 간선의 수를 의미합니다.
연관 문제 (내일 DFS, BFS 모두 풀이과정 추가할 예정)
DFS와 BFS : https://developer-mac.tistory.com/63
연결 요소 : https://www.acmicpc.net/problem/11724
이분 그래프 : https://www.acmicpc.net/problem/1707
섬의 개수 : https://developer-mac.tistory.com/66
단지번호붙이기 : https://www.acmicpc.net/problem/2667
섬의 개수 : https://www.acmicpc.net/problem/4963
BFS 연습 문제
토마토1 : https://developer-mac.tistory.com/67
토마토2 : https://developer-mac.tistory.com/68