그래프 문제의 종류는 상상 이상으로 많습니다.
DFS, BFS의 선택은 그저 상황에 맞게 하면 될 뿐입니다. 마치 그래프를 인접 행렬, 혹은 인접 리스트 방식으로 상황에 맞게 표현하는 것처럼요.
DFS로는 해결 불가에 가까운 문제가 BFS로는 보다 쉽게 해결될수도, 그 반대의 상황이 나올수도 있습니다.(물론 두 알고리즘만 가지고서는 시도조차 못할만한 문제들도 상당히 많죠)
단순히 BFS알고리즘 하나만 놓고 보면은 그 한계가 명확합니다.
그리고 "시험장에 그래프문제"가 어떤 시험장을 말씀 하시는건지 모르겠지만 BFS는 만능이 아닙니다.
태그하신 문제도 DFS에 약간의 테크닉만 더해지면 직관적이고 간단하게 해결방법을 찾을 수 있습니다.(이 문제에선 "백트래킹"이라고 하는 기법입니다. 물론 BFS로도 해결 가능)
그저 이런 저런 유형들을 많이 접해보고, 배울 것이 있다면 배우며 익숙해지면 될 뿐입니다.
black01676 1년 전
이 문제도 DFS 카테고리로 들어있긴한데
제가 그래프문제를 DFS로 어떻게 풀어야하는지 잘 감이 안잡혀서 보통 BFS로 접근해서 풀고는 했습니다.
그래서 시험장에 그래프문제는 BFS 풀려고 하는데
혹시 DFS로만 푸는 2차원 그래프 문제도 있을까요?
개인적으로 DFS는 return하는 조건을 생각하는게 문제마다 너무 다르기도하고, BFS처럼 패턴이 정해져있지 않은 것 같아서 어렵네요ㅠㅠ
팁부탁드립니다.