[이론][완전탐색][DFS] Chapter 0

완전탐색의 두 번째 알고리즘 DFS 문제를 풀어보겠습니다.


DFS는 개념은 생략하고 코드에서의 스킬을 학습하겠습니다.

DFS : 코드

DFS : 기본 코드

DFS의 기본 코드는 여기에서 확인할 수 있습니다. 일반적으로는 DFS를 하나의 노드에서 시작해서 갈 수 있는 마지막 노드까지 진행합니다.

DFS : 모든 DFS 경로

마지막 노드까지 진행하고 백트래킹 방식을 적용해서 또 다른 DFS 경로르 구하기 위해서는 visited[curr] = false;를 dfs()를 호출한 뒤 추가하면 됩니다.

DFS : DFS의 길이

DFS의 길이를 구하는 방법은 두 가지를 제시합니다.

  1. 전역변수를 사용하는 방법은 여기
  2. 지역변수와 return을 사용하는 방법은 여기

지역변수를 사용하는 방법에서 ans의 값이 1초 초기화되는 것은 dfs(curr)가 호출될 떄 curr 한 개는 최소 dfs의 요소로 포함되기 때문입니다.

Leave a comment