DFS와 BFS
DFS와 BFS를 코딩테스트 관점에서 비교하고 서술해보려한다.
많은 사람들이 처음 코딩테스트 공부를 하면서 두 알고리즘을 써야하는 상황에 대해 헷갈리곤 한다.
낮은 난이도의 문제는 둘 중 어느 알고리즘을 써도 풀리는 경우가 많기 때문에
난이도가 높아지고 나서 헷갈려 어디부터 다시 공부해야 하나 걱정하는게 아닌가 생각이 들었다.
우선 DFS, BFS는 깊이/너비 를 우선적으로 '탐색'하는 알고리즘으로
그래프, 트리 형태의 구조에서 서로의 연결성을 기반으로 탐색해 결과를 도출하는 알고리즘이다.
https://namu.wiki/w/%EA%B9%8A%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89
깊이 우선 탐색
Depth First Search, DFS 그래프 순회 방식의 일종. 거의 항상 너비우선탐색(BFS; Breadt
namu.wiki
https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89
너비 우선 탐색
Breadth First Search, BFS 너비 우선 탐색 은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐
namu.wiki
두 알고리즘에 대해서는 위 링크를 참고하면 간단한 이해가 가능하고
본 글에서는 문제 접근에 관해서 집중해보겠다.
알고리즘 문제 접근 방식에서는 수행시간이 중요한데
DFS는 깊이가 무한한 경우 사용이 어렵고
BFS는 가장 끝 노드에서 무언가를 확인한 후에 경로를 사용할지 말지 결정하는 경우에 사용하기 어렵다.
DFS는 재귀함수를 사용하고 BFS는 Queue를 사용한다는 점에서 비슷한 탐색이지만 코드의 모양이 차이가 난다.
탐색문제를 제외한 DFS의 대표적인 문제는 순열, 조합 문제이다.
N개의 숫자를 '순서에 맞게' 순열과 조합으로 출력하기 위해서는 물론 다른 방법으로 찾아낸 후 정렬해도 괜찮지만
DFS를 사용하는 경우 다음 올 숫자에 대해 +1 시키면서
중복을 방지하는 경우 boolean 배열 하나를 더 참고하여 재귀함수를 반복시키면 간단하다.
순열, 조합을 dfs와 다르게 분류할 수도 있겠지만 구조가 다르지 않아 같은 알고리즘으로 이해하고 공부했다.
아래 문제는 구현 + 순열 문제로 간단히 풀 수 있다면 순열문제는 앞으로 공부하지 않아도 되겠다.
https://www.acmicpc.net/problem/17281
17281번: ⚾
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종
www.acmicpc.net
대부분의 순열 문제는 depth가 9가 넘어가지 않을 것이다.
이는 알고리즘 문제의 제한시간 때문에 재귀로 순열을 만들어 낼 때 생기는 제약 조건이다.
이것을 조금 바꿔 말하자면 DFS로 풀어야겠다고 생각했지만 depth가 9가 넘어간다면
다른 조건은 없는지, 알고리즘 선택을 다시해야하는지 고민해보아야 한다는 뜻이다.
물론, depth가 깊더라도 트리, 그래프의 노드 수가 많지 않다면 충분히 가능하다.
DFS를 탐색에 사용하는 경우는 마지막 노드의 조건을 확인한 후 이전 분기로 복귀하는 경우이다.
이전 분기로 복귀하면서 특정 로직을 수행하는 경우도 있고
수정되었던 상황을 원복해야하는 경우도 있다. (백트래킹)
삼성 기출문제 중 DFS + 구현 문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
풀이
https://code-beat.tistory.com/3
[Code Tree] 삼성 SW 역량테스트 기출 풀이
취업 준비를 위한 코딩테스트를 손 놓은지 근 3년 만에 SSAFY 임직원 멘토링을 하려면 다시 기출은 풀 수준은 되어야 하지 않을까 싶어서 최근 기출 문제를 풀어봤다. (입사 후 프로 등급도 취득했
code-beat.tistory.com
BFS를 많이 사용하는 경우는 미로찾기와 같은 경로를 찾는 경우이다.
너비 우선이기 때문에 root 노드로 부터 같은 거리에 있는 노드를 동시?에 탐색한다는 개념으로 접근하면
상하좌우로 동시에 번식한다는 문제와 같은 조건이 달린 문제에 접근하기 편하다.
DFS를 사용하는 경우에는 꽤 복잡하게 해결해야 할 것이다.(사실 해결이 가능한 지 생각해보지도 않았다.)
이렇게 특정 노드로부터 거리를 구하거나 최단 거리로 어느 노드에 도달하는 문제의 경우에는 BFS를 사용하면 된다.
아래 문제를 간단히 해결한다면 코딩테스트를 준비하면서 BFS를 이해하기에는 충분한 수준이 되었다고 생각한다.
https://www.acmicpc.net/problem/1194
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
삼성기출문제 중 최단경로 + 구현 문제
https://www.acmicpc.net/problem/19238
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
처음 삼성전자 코딩테스트를 통과 했을 때는 DFS + 구현 문제만 마스터한다는 각오로 공부해 시험에서 한 문제만 풀었다.
지금은 두번째 문제가 이전과 다른 경향을 가지고 있지만 결국 출제되는 알고리즘의 수준이 완전 달라진 것은 아니기에
코딩테스트를 어떻게든 통과해보겠다고 생각하면
DFS, BFS + 구현(시뮬레이션) 문제를 마스터해보자.
DFS, BFS 문제는 다른 코딩테스트에서도 중간 혹은 그 이상의 수준의 난이도로 출제되기 때문에
네이버, 카카오의 중간이상의 번호 문제에서 꼭 한 두문제씩 출제되므로
코테를 치려는 취준생이라면 무조건 이해하고 풀어내야하는 알고리즘 문제들이다.
** 알고리즘의 난이도는 사소한 조건에 의해 결정된다. 이 점을 꼭 확인하면서 풀이하고 리뷰하도록 하자.