9. [Java] DFS (깊이 우선 탐색)

⭐️ DFS (Depth First Search)

• 정해진 규칙에 의해 시작 정점에서 멀어지는 방향 우선으로 탐색하는 방법
• 일반적으로 재귀함수를 사용해서 구현한다. (Stack으로도 구현 가능하지만, 구현이 상당히 복잡해진다.)
• 그래프가 트리 형태일 때, DFS 알고리즘이 자주 쓰인다.
• 최단거리를 구하기에는 적합한 알고리즘이 아니다. (시간 초과 주의)
• 재귀로 구현된다는 점에서 Backtracking 과 유사하다.

📝 DFS (Depth First Search) 탐색 구현 방법

• 방문 체크 용 (재방문 방지) 배열을 만든다.
• 현재 정점을 파라미터로 넘겨 받는 함수(메소드)를 정의한다.
• 함수(메소드) 내부에서..
  • 현재 정점이 이미 방문한 정점이면 return 한다.
  • 현재 정점의 방문 체크를 한다.
  • 해당 정점에서 방문 가능한 다음 정점을 파라미터 넘기면서 현재 함수를 재귀 호출한다.
    • (필요한 경우) 해당 정점이 유효한 정점인지 체크한다.
    • (필요한 경우) 해당 정점으로 이동 가능한지 체크한다.

Tip) 가중치가 같으면 BFS 사용, 가중치가 다르면 다익스트라 사용