DFS문제, 접근 전략

DFS문제에서 어려울 수 있는 부분은 재귀함수의 동작 원리를 알아야만 문제를 풀 수 있다는 점 입니다. DFS 알고리즘에서 어떻게 재귀함수를 활용하는지를 중점으로 설명드리겠습니다.

 

기본구조 & 탐색과정

def dfs(v):   //O(E)
  백트래킹 관계없이 v 방문 시 수행할 코드
  if visited[v] ==1:  //백트래킹 조건
     return
  visited[v] =1 //(깊이 탐색하기 전 v 에서 수행할 코드)
  if/for 추가적인 탐색 조건  //탐색 우선순위가 높은 경우
     dfs(i)
  for i in graph[v]:  //인접노드 탐색   
     dfs(i)
  //깊이 탐색한후 v에서 수행할 코드

기본이 되는 DFS 코드를 분석하면 3부분으로 나눌 수 있습니다.

• if문(백트래킹 조건)
• 방문한 노드에서 수행할 코드
• for문(인접 노드 탐색)

즉, 백트래킹 조건이 만족하지 않으면 해당 노드를 방문한다고 볼 수 있고 방문한 노드에서 수행할 코드를 작성합니다. 방문 후 인접 노드에 대한 탐색은 for문을 통해 이루어집니다. 재귀함수의 특징을 볼 수 있는 부분은 for문 안의 dfs(i)가 호출되면 i가 처음 v의 역할을 하게 된다는 점입니다. 또한 for문 이후의 코드는 dfs(i)를 재귀적으로 호출하는 모든 코드가 실행된 후에 (개념적으로 처음 v 노드까지 되돌아 온 후) 최종적으로 실행됩니다.
코드가 어떤 순서로 실행되는지 이해하는 것이 중요하며, 이는 재귀함수의 호출과 관련됩니다.

 

문제에 따라 달라지는 부분 (중요)

1) 추가적인 백트래킹 조건 & 탐색 조건

어떤 노드를 방문했을 때 탐색하지 않을 조건은 처음 if문에 작성하게 됩니다.

if visited[v] ==1 or 추가적인 조건:  //백트래킹 조건
     return

추가적인 탐색조건이 있는 경우 if문(혹은 for) 안에 dfs(i)를 통해 탐색하게 됩니다. 이 때 기존 for문 위에 작성하면, 탐색 우선순위가 높다는 것을 알 수 있습니다. 물론 아래에 작성하면 탐색 우선순위가 낮은 것입니다. 같다면 기존 for문에 조건을 추가하면 됩니다.

if/for 추가적인 탐색 조건 
     dfs(i)

2) 방문한 노드에서 수행할 코드
  기본구조에서는 방문처리만을 하기 때문에 응용문제를 풀지 못 합니다. 이 부분에서 방문한 노드를 리스트에 추가해 현재까지의 경로를 추적하거나 연산을 수행해 현재까지의 연산결과 추적할 수 있습니다.
  이를 위해서는 dfs(v)에서 노드 이외에 추가적인 입력 파라미터가 필요합니다. 경로를 추적하는 경우 일반적으로 list를 함께 입력하는데, 생각처럼 경로가 저장되지 않는 경우가 있습니다. 이는 list가 mutable 객체로 dfs 입력파라미터로 전달될 때 deepcopy 되지 않기 때문입니다. 이 때는 copy.deepcopy()를 사용해 입력하면 됩니다.

---

DFS 문제에서 필요한 개념에 대해 정리하였고, 이를 코드에 적용한 풀이를 이후 포스팅에 업로드 하도록 하겠습니다. 개념이 당장 이해되지 않아도, 실제 문제와 코드를 보면 이해가 될 것입니다.