BFS, DFS 탐색 팁

저는 항상 BFS 문제를 풀 때 구현을 다한 뒤 테스트 케이스를 다 통과하고 맞왜틀을 정말 많이 겪었습니다. 한 번 갇힌 사고에서는 탈출하기 정말 어려운 게 알고리즘 문제이고 이러한 경우를 어떻게 하면 줄일 수 있을까 정말 많이 고민했습니다.

그래서 저의 안좋은 습관을 찾고자 노력하였고 치명적이 안 좋은 습관을 한 가지 찾았습니다.

안 좋은 습관은 BFS 탐색의 조건절에서 저는 "찾고자 하는 경우"를 조건으로 넣어주는 습관을 가지고 있었습니다.

"이게 뭔소리냐 찾고자 하는 경우를 조건으로 넣는 게 왜 안 좋은 습관이냐?"라고 하실 수 있습니다. 하지만 찾고자 하는 경우를 찾는 것보다는 안 되는 경우를 찾는 게 더 쉽고 정확합니다. 밑에 문제로 예시를 들어보겠습니다.

 

백준 https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

이 문제에서는 처음에 BFS로 승객을 찾고 승객의 도착지를 BFS로 두 번 탐색해야 합니다.

저의 코드 중 승객의 도착지를 찾는 조건 부분입니다. 밑에 문제 해결 코드는 틀렸습니다.

밑에는 첫 번째 작성 코드를 변경한 것입니다. 검은 줄 부분을 변경하였고 통과 처리가 되었습니다.

위 문제에서 -1은 벽을 의미하는데 도착지가 되는 경우의 예외처리를 시도하려다가 오히려 정답처리가 안되었습니다. 이유는 모르겠습니다. 이처럼 알고리즘 문제에서 가능한 경우의 수를 전부 생각해내는 것보다는 문제에서 주어지는 불가능한 경우만 조건으로 막는 것이 훨씬 더 유리하다는 생각을 하게 되었습니다. 보통 문제에서 BFS 탐색 시 경계값, 벽, 물 같은 탐색이 불가능한 경우가 주어집니다. 이런 경우만을 예외처리해주는 것이 더 정확하지 저처럼 가능한 경우만을 넣어주려고 하는 방식은 그 안의 숫자 값에 따라 생길 수 있는 위험성이 너무 많습니다. 문제에 따라 다른 경우가 존재하고 취향이 갈리겠지만 저는 이런 방식으로 문제를 접근하기 시작하다 보니 BFS문제의 정답률이 상승한 거 같습니다.