BFS/DFS 는 어떤 상황에 적합한거지?! 🧐

그래프와 BFS/DFS 코딩 테스트를 풀다 보면 어떤 문제는 BFS가 적절하고, 어떤 문제는 DFS 이고 어쩔 땐 둘 다 가능한 경우가 있다.

이 경우를 헷갈리지 않기 위해 상황 별 정리를 해본다.

이 글 에서 그래프의 최단경로를 구하는 방법이 잘 정리되어 있어서 참고했다.

 

1. BFS

너비 우선 탐색으로, 그래프에서 쓰일 수 있는 탐색 알고리즘이다. 

BFS는 '가중치가 없는 그래프의 최단경로를 찾는 경우'에 사용될 수 있다. 그래서 최단거리의 합(또는 길이)를 출력하거나 최단 거리의 경로가 무엇인지 출력하는 문제에 적합하다.

1. 최단거리를 출력하는 방법
   • 새로운 노드를 탐색할 때, 그 전 단계의 거리에 +1 을 해주면 된다.

   • 

2. 최단거리 경로를 출력하는 방법
   • 직접 풀어보고 적기

 

2. DFS

 

3. 구현 시 도움되는 것들

• 최대 거리 또는 최소 거리 출력할 때 count 비교하면서 리스트에 저장하기 (다 저장하지말고)
• 경로 리스트 출력할 때 print(*list) 하면 값만 출력됨.