그래프 탐색 알고리즘
DFS와 BFS 모두 그래프 탐색 알고리즘으로, 여러 개체들이 연결되어 있는 자료구조에서 특정 개체를 찾기 위한 알고리즘으로 이해 가능 !
대표적인 문제 유형으로:
1. 경로탐색 유형 (최단거리, 시간)
2. 네트워크 유형 (연결)
3. 조합 유형 (모든 조합 만들기)
DFS: 깊이 우선 탐색
특정 개체만 끝까지 파는 유형으로, 재귀함수가 가장 일반적
재귀를 타고 타고 타서 탈출 조건에 먼저 도달하고 다음 파라미터를 하나씩 바꿔가면서 정답을 찾아가는 방식.
시험에서 자주 등장하는 DFS 문제 유형은
- 경로 찾기
- 연결 요소: 현재 노드를 기준으로 연결된 모든 노드를 탐색하는 문제
- 플러드 필: 그래프의 영역을 특정 색상으로 채우는 문제 (땅따먹기)
- 백트랙킹: 해를 찾는 도중에 막히면, 되돌아가서 다시 해를 찾아가는 기법
- 그래프 순회: 임의의 한 노드에서 시작하여 모든 노드들을 한 번씩 방문하는 작업
- 사이클 찾기: 시작점과 방문점이 같은 경우가 존재하는지 찾는 문제
BFS: 너비 우선 탐색
여러 개체를 하나씩 파보면서 가는 유형으로 Queue나 LinkedList로 구현하는 것이 일반적
BFS는 턴을 돌면서
1. 가장 먼저 넣었던 것을 꺼내서
2. 연결된 점을 Queue에 넣고
3. Queue가 빌 때까지 반복
-> 순서가 보장되어야 하기 때문에 위의 자료구조를 사용할 수 밖에 없음.
시험에서 자주 등장하는 BFS 문제 유형은
- 기본 순회: 현재 노드를 기준으로 이동할 수 있는 모든 노드를 탐색하는 문제
- 최단 경로: 득정 두 노드 사이의 최단 경로를 탐색하는 문제
- 연결 요소: 현재 노드를 기준으로 연결된 모든 노드를 탐색하는 문제
- 플러드 필: 그래프의 영역을 특정 색상으로 채우는 문제 (땅따먹기)
코테에서 DFS? BFS?
보통 경로 찾기, 연결 요소, 플러드 필의 경우 BFS, DFS 둘 중 하나 잡고 풀어도 상관없음.
그럼에도 DFS를 추천하긴 함.
-> 동작 검증이 쉬움.
DFS의 경우 하나의 조합을 완성해서 정답과 비교하고, 또 다른 조합을 완성해서 정답과 비교해보기 때문에 정답을 비교하는 시점에서 기대한 대로 조합이 잘 나왔는지 확인이 쉬움.
BFS는 한 번에 여러 조합들을 한칸한칸 만들어보다보니 조합이 완성되어서, 정답을 비교하는 시점에 언제 어덯게 이렇게 만들어졌지, 어디서부터 틀렸지? 확인이 어려움.
다만, DFS는 한 놈만 패는 알고리즘이라 그 한 놈이 악질이면 시간이 초과될 수 있음 -> 수행 시간 관점에서 복불복.
물론 운이 좋으면 첫번째 조합이 최적의 답이 될 수 있으나, 최악의 경우 모든 조합을 만들어야 할 수도 있음.
하지만 BFS의 경우, 한 번씩 패고 가는 알고리즘이라 물론 초반엔 느려보일 수 있지만 하나의 정답을 찾으면 나머지 경우는 정답에서 제외 -> 시간복잡도가 낮음.
