BFS & DFS 구분하자!

BFS & DFS (그래프 알고리즘)

BFS & DFS. 삼성 SW 역량테스트에 핵심 주제이다.

하지만, 이것만 잘 알고 코드를 구현한다고 테스트 케이스가 다 통과하는가? 

답은 "아니다."

이유는 재귀 함수는 쉬운 것이고, 이와 관련된 코드를 구현하는 것, 

시뮬레이션 작업이 더 어렵기 때문이다.

그렇다면 왜? 탐색 알고리즘에 집중해 있는지 알아보자.

탐색 알고리즘은 순회를 모두 하는 경우이기에, 연산량이 많고 그에 따라, 컴퓨터 활용이 많아진다.

따라서, 기업에서 SW개발 직군을 뽑을 때, 컴퓨터 연산량을 잘 관리하고 효율적으로 코드를 짜는 사람을 

뽑으려 하므로 탐색 알고리즘이 코드 구현에 핵심 요소라고 할 수 있다.

기본적으로 탐색은 컴퓨터 연산량을 극대화하는 작업이기에, 사람이 코드를 구현하고 디버깅하면서 

문제를 파악하는 것은 쉽지 않다.

그렇기 때문에, 처음부터 설계를 꼼꼼하게 하고 예외적인 상황이 발생할 지에 대해서 고민한 다음 

코드를 구현해야 한다.

즉, 처음 코드를 짜고 나서부터 완성할 때까지 코드 수정을 최소화해야 한다는 것이다.

탐색 알고리즘을 구현할 때, 가령, DFS 구현 시, 반드시 주의해야할 점은 DFS에서는 스택 또는 재귀 코드만 

구현해야 한다는 것이다.

구현 과정, 시뮬레이션 코드는 별도의 함수를 만들어서 정리하면서 코드를 짜야 한다.

재귀함수 안에서 조건에 대한 시뮬레이션을 모두 구현한다면, 더 복잡해지고 디버깅도 힘들 것이다.

따라서 반드시 설계를 잘 해놓고 코드를 짜도록 하자.

---

BFS와 DFS의 차이는 다들 너비우선순회, 깊이우선순회로 알고 있을 것이다.

(Queue) vs (스택 or 재귀함수) 만으로 이해하고 코드를 짜는 사람도 상당히 많을 것이다.

하지만 중요한 것은, 이 차이만을 가지고 문제에 접근할 경우, 풀리는 문제가 있고 풀었는데 런타임에러로 

틀리는 경우가 발생할 것이다.

BFS는 너비우선탐색으로 현재 나의 위치에서 가장 가까운 노드를 먼저 방문하는 것이다.

방문하면서 현재 위치는 pop해주고 방문한 곳은 체크한 뒤, 방문할 곳은 큐에 넣는 과정입니다.

따라서, 미로 탐색과 같은 알고리즘은 최단 거리만을 가지고 탈출하는 것이기에 BFS가 적합합니다.

하지만 가령, 미로탐색을 진행하는데, 이동할 때마다 가중치가 붙어서 이동한다거나, 이동 과정에서 

여러 제약이 있을 경우, DFS로 구현하는 것이 좋습니다.

탐색 시간은 더 걸리긴 하지만, 가중치에 대한 변수를 지속해서 관리할 수 있다는 장점이 있으므로 

코드 구현 시, 더 편리하기 때문입니다.

이상 BFS와 DFS 관련 내용을 포스팅하였고, 다음 포스팅에서는 직접 관련 문제들을 소개해드리도록 하겠습니다.