[코딩테스트 합격자 되기 파이썬] 1주차 스터디 - DFS

1. DFS를 구현하는 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는 것입니다. 각 구현 방식의 장단점을 비교 설명해주세요

1. 재귀 호출을 이용한 DFS

장점:

• 간결하고 직관적: 재귀 호출을 사용하면 코드가 간단해지고, DFS의 기본 개념(현재 노드에서 다음 노드로 자연스럽게 진행)을 직관적으로 표현할 수 있습니다.
• 내장 스택 활용: 프로그래밍 언어의 함수 호출 스택을 활용하기 때문에 별도의 자료구조를 구현할 필요가 없습니다.

단점:

• 스택 오버플로우 위험: 탐색 깊이가 매우 깊거나 그래프가 크면 함수 호출 스택이 넘칠 수 있습니다.
• 제어의 한계: 재귀 과정 중에 스택 상태를 직접 제어하기 어렵기 때문에, 특정 상황에서 세밀한 제어가 필요한 경우에는 유연성이 떨어질 수 있습니다.
• 디버깅 어려움: 재귀 호출이 복잡해지면 호출 스택을 추적하며 디버깅하기 어려울 수 있습니다.

---

2. 명시적인 스택을 이용한 DFS

장점:

• 스택 오버플로우 회피: 직접 스택 자료구조를 관리하므로, 재귀 호출에 비해 스택의 크기를 유연하게 조절할 수 있으며, 스택 오버플로우 위험을 줄일 수 있습니다.
• 세밀한 제어: 스택의 동작을 직접 관리할 수 있어, 탐색 순서나 조건을 더욱 세밀하게 조정할 수 있습니다.
• 반복문 기반 구현: 반복문을 활용하기 때문에, 재귀 호출의 오버헤드(함수 호출 비용)를 줄일 수 있고, 일부 언어에서는 성능 면에서 유리할 수 있습니다.

단점:

• 코드 복잡도 증가: 명시적으로 스택을 구현하고 관리해야 하므로, 코드가 재귀 방식에 비해 다소 복잡해질 수 있습니다.
• 가독성 저하: DFS의 기본 개념은 동일하지만, 스택 자료구조를 사용하는 구현은 재귀 방식보다 읽기 어려울 수 있습니다.

---

결론

• 재귀 호출 방식은 코드가 간결하고 이해하기 쉽지만, 탐색 깊이가 깊어질 경우 스택 오버플로우의 위험이 있습니다.
• 명시적인 스택 방식은 스택 오버플로우 문제를 회피할 수 있고, 더 세밀한 제어가 가능하지만, 구현이 복잡해지고 가독성이 떨어질 수 있습니다.

 

2. 방향 그래프(Directed Graph)에서 사이클(Cycle) 존재 여부를 판별하기 위해 DFS를 어떻게 활용할 수 있는지 구체적인 알고리즘을 설명해주세요

1. 기본 아이디어

DFS를 수행하면서 각 노드의 방문 상태를 관리하는데, 두 가지 주요 정보를 사용합니다.

• 방문 여부 (visited): 해당 노드를 한 번이라도 방문했는지 여부를 표시합니다.
• 재귀 호출 스택 (recursion stack) 또는 현재 경로 (path): 현재 DFS 호출 경로에 포함된 노드들을 추적합니다.

방향 그래프에서는 사이클이 존재하면 DFS 도중 이미 현재 경로에 있는 노드를 다시 방문하게 됩니다. 이 때, 만약 현재 DFS 경로에 포함된 노드를 다시 만나면 사이클이 존재한다고 판단할 수 있습니다.

---

2. 알고리즘 단계

1. 초기화:
   • 모든 노드에 대해 visited[node] = False로 설정합니다.
   • 모든 노드에 대해 recStack[node] = False로 설정합니다. (또는 재귀 호출 중인 경로를 추적할 자료구조 사용)
2. 모든 노드에 대해 DFS 실행:
   • 아직 방문하지 않은 노드에 대해 DFS를 호출합니다.
3. DFS 함수 내부:
   • 현재 노드를 방문 상태로 표시: visited[node] = True
   • 현재 노드를 재귀 스택(경로)에 추가: recStack[node] = True
   • 현재 노드와 인접한 모든 이웃 노드에 대해 다음을 수행:
     • 만약 이웃 노드가 아직 방문하지 않았다면, 해당 노드에 대해 DFS를 재귀 호출합니다.
     • 재귀 호출 결과 사이클이 검출되면, 바로 사이클 존재를 반환합니다.
     • 만약 이웃 노드가 이미 방문되었고, 동시에 현재 DFS 경로(재귀 스택)에 있다면, 사이클이 검출된 것입니다.
   • 현재 노드에 대한 모든 처리가 끝나면, DFS 경로에서 노드를 제거: recStack[node] = False
   • 사이클이 발견되지 않으면 DFS 함수를 종료하며, 사이클이 없음을 반환합니다.
4. 결과 반환:
   • 모든 DFS 호출이 완료된 후에도 사이클이 한 번도 검출되지 않았다면, 해당 그래프는 사이클이 없는 것으로 결론 내립니다.

---

3. 의사코드(Pseudocode)

python

복사

def isCyclic(graph): # graph: 각 노드와 인접 노드들의 리스트(또는 딕셔너리) visited = {node: False for node in graph} recStack = {node: False for node in graph} def dfs(node): visited[node] = True recStack[node] = True for neighbor in graph[node]: if not visited[neighbor]: if dfs(neighbor): return True elif recStack[neighbor]: # 현재 경로에 이미 포함된 노드를 다시 방문 return True recStack[node] = False return False for node in graph: if not visited[node]: if dfs(node): return True # 사이클 존재 return False # 사이클 없음

---

4. 알고리즘 설명

• 재귀 스택 활용: DFS의 재귀 호출 중에 recStack을 통해 현재 탐색 경로에 있는 노드를 추적합니다. 이때, 경로에 있는 노드를 다시 방문하면 사이클이 있는 것입니다.
• 방문 여부 관리: visited 배열을 사용하여 이미 방문한 노드를 다시 DFS 호출하지 않도록 하여, 중복 탐색을 방지하고 성능을 최적화합니다.
• 시간 복잡도: 모든 노드와 간선을 한 번씩 탐색하기 때문에, 시간 복잡도는 O(V+E)입니다.
• 공간 복잡도: 방문 배열과 재귀 스택에 O(V)의 공간이 필요합니다.

 

3. 재귀를 활용한 DFS에서 가장 최근의 노드로 돌아가는 백트래킹 동작이 어떤 방식으로 동작하는지 하나의 예를 들어 설명해주세요

DFS(깊이 우선 탐색)에서 재귀 호출로 탐색을 진행할 때, 더 이상 진행할 수 없거나 모든 인접 노드를 방문한 경우에는 현재 호출된 함수가 종료되면서 바로 이전의 호출(즉, 부모 노드의 탐색)으로 돌아가게 됩니다. 이를 백트래킹(backtracking)이라고 부릅니다. 아래 예시를 통해 구체적으로 설명드리겠습니다.

• 노드 A의 인접 노드: B, C
• 노드 B의 인접 노드: D
• 노드 C와 노드 D는 인접 노드가 없음

---

DFS 재귀 호출 및 백트래킹 과정

1. 시작: DFS(A) 호출
   • A를 방문합니다.
   • A의 첫 번째 인접 노드인 B로 DFS 호출을 진행합니다.
2. DFS(B) 호출
   • B를 방문합니다.
   • B의 인접 노드인 D로 DFS 호출을 진행합니다.
3. DFS(D) 호출
   • D를 방문합니다.
   • D는 인접 노드가 없으므로, DFS(D)는 더 이상 진행할 노드가 없다고 판단하고 함수를 종료합니다.
   • 함수 종료 시점에서 DFS는 D의 호출 스택을 제거(백트래킹)하고, 호출했던 부모인 B로 돌아갑니다.
4. 백트래킹 후 DFS(B)로 복귀
   • DFS(B)는 D 외에 더 방문할 인접 노드가 있는지 확인합니다.
   • 만약 다른 인접 노드가 없다면, DFS(B) 역시 함수를 종료하고, 호출했던 부모인 A로 돌아갑니다.
5. 백트래킹 후 DFS(A)로 복귀
   • DFS(A)는 B 외에 다른 인접 노드인 C가 남아 있음을 확인합니다.
   • C로 DFS 호출을 진행합니다.
6. DFS(C) 호출
   • C를 방문합니다.
   • C는 인접 노드가 없으므로, DFS(C)는 종료됩니다.
   • DFS는 C의 호출 스택을 제거하고, 최종적으로 DFS(A)도 종료됩니다.

---

백트래킹 동작 정리

• 재귀 호출 스택: DFS를 수행할 때 각 노드에 대한 호출은 스택에 쌓입니다.
  • 호출 순서: DFS(A) → DFS(B) → DFS(D)
• 백트래킹: DFS(D)가 종료되면, 함수 호출 스택에서 D가 제거되면서 DFS(B)로 되돌아갑니다. 같은 방식으로 DFS(B)가 모든 인접 노드를 다 확인하면 다시 DFS(A)로 돌아갑니다.
• 즉, 재귀 함수가 종료될 때마다 스택에서 제거(팝)되어 바로 이전 호출(즉, 가장 최근의 부모 노드)로 제어가 넘어가는 것입니다.