반응형
개념문제
- DFS를 구현하는 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는 것입니다. 각 구현 방식의 장단점을 비교 설명해주세요.
더보기1. 재귀
재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 DFS에 적용하여 구현하게 된다.
장점 : 코드의 간결함, (호출 스택이 DFS의 진행 과정을 자연스럽게 관리)
단점 : 스택오버플로우 발생 가능성이 높다, (함수 호출 오버헤드로 인한 성능 저하).
직접 문제를 풀면서 느꼈던 재귀 함수와 DFS의 장단점은 코드가 간결한 만큼, 스택오버플로우(시간초과, 메모리초과) 발생 확률이 타 문제들보다 많았다는 점이다. 메모리초과가 나지 않으면 시간초과로 이어지는 경우가 많았다.
괄호 내 내용은 각종 AI툴들에게 해당 질문을 하였더니 공통된 답변을 하여 작성하였다.
2. Stack
스택은 박스를 쌓아 올리듯 먼저 쌓인 데이터는 나중에 꺼내오게 되는 특성을 활용하여 DFS를 구현하게 된다.
장점 : 스택오버플로우 발생 가능성이 낮다.
단점 : 구현 과정이 길다.
처음에 이 문제를 맞닥뜨렸을 때, 가장 먼저 생각한 각 구현 방법에 있어서 장단점은 코드의 간결함 vs 스택오버플로우 였다. 백준 문제를 풀때, 재귀로 스택오버플로우가 발생하면 스택으로 바꿔서 풀었던 경험이 종종 있었다. 나중에 백트래킹도 같이 공부하게 되겠지만, 이때를 위해서라도 지금 공부를 조금 더 철저히 할 필요가 있다.
구현 관련해서는 아래 [풀어볼 문제 1. 깊이 우선탐색 순회]에서 알아보도록 하자. - 방향 그래프(Directed Graph)에서 사이클(Cycle) 존재 여부를 판별하기 위해 DFS를 어떻게 활용할 수 있는지 구체적인 알고리즘을 설명해주세요.
더보기Leetcode 문제 중 'Course Schedule' 를 예시로 들어서 설명.
https://leetcode.com/problems/course-schedule/
prerequisites[i] = [ai, bi] 이며, ai를 수행하기 위해서는 bi를 들은 적이 있어야 한다.
class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: visited = [0] * numCourses pre = defaultdict(list) for course, p in prerequisites : pre[course].append(p) def dfs(node) : visited[node] = 1 for neighbor in pre[node] : if visited[neighbor] == 0 : if dfs(neighbor) : return True elif visited[neighbor] == 1 : return True visited[node] = 2 return False for node in range(numCourses) : if visited[node] == 0 : if dfs(node) : return False return True
해당 문제는 방향 그래프이면서 순환하는 그래프인지 판단하는 문제로, DFS를 활용하여 순환하는 그래프가 존재하는지에 대해서 알아볼 수 있다.
[1] 현재 방문중인 노드를 방문 표시
[2-1] 인접한 노드를 방문한 적이 없으면, dfs(neighbor)를 통하여 다시 방문 중 처리를 한다. 재귀이기 때문에 이를 반복
[2-2] 인접한 노드를 방문 중이면, True를 반환한다. => 이때 True는 순환하고 있음을 의미한다.
[3] [2-1] 에서 모두 False 이 된다면, node를 방문 완료 처리를 하며 dfs함수를 False 를 반환한다. => 이때 False는 순환하고 있지 않음을 의미한다.
[4] 모든 노드를 방문하면서 dfs(node)에서 순환이 발견하면 해당 문제는 존재하지 않음을 의미하며 False를 반환하고, 그렇지 않다면 True를 반환한다.
사실 이 문제를 풀어보면서, 각종 AI툴에 순환 하는 코드를 물어보고 Leetcode 상에 있는 솔루션들을 보면서 머리 속으로 "visited배열을 만들어서 해결하면 되지 않을까?"라고 막연하게 생각했던 부분이 이런 식으로 구현하는 방법도 있다는 것을 알 수 있었다. 아직 이 방법에 대해서 조금 더 공부해 볼 필요가 있다. - 재귀를 활용한 DFS에서 가장 최근의 노드로 돌아가는 백트래킹 동작이 어떤 방식으로 동작하는지 하나의 예를 들어 설명해주세요.
더보기책 p.383 에 나오는 재귀 함수를 활용한 깊이 우선 탐색을 예시로 들면, 그림체는 책을 참고하면 좋을 것이다.
graph = { '1' : ['4', '5'], '2' : ['3'], '3' : [], '4' : ['2', '3'], '5' : ['1', '4'], } visited = set() path = [] def dfs(node, depth) : indent = ' ' * depth print(f'{indent}노드 "{node}" 방문 시작') visited.add(node) path.append(node) print(f'{indent}현재 경로: {" -> ".join(path)}') for neighbor in graph[node] : if neighbor not in visited : print(f'{indent}이웃 노드 "{neighbor}"로 이동') dfs(neighbor, depth + 1) print(f'{indent}노드 "{neighbor}"에서 노드 "{node}"로 백트래킹') path.pop() print(f'{indent}노드 "{node}" 방문 완료 (백트래킹 후 경로: {" -> ".join(path) if path else "빈 경로"})') print("DFS 탐색 시작 (백트래킹 과정 시각화): ") dfs('1', 0) print("\nDFS 탐색 완료")
DFS 탐색 시작 (백트래킹 과정 시각화): 노드 "1" 방문 시작 현재 경로: 1 이웃 노드 "4"로 이동 노드 "4" 방문 시작 현재 경로: 1 -> 4 이웃 노드 "2"로 이동 노드 "2" 방문 시작 현재 경로: 1 -> 4 -> 2 이웃 노드 "3"로 이동 노드 "3" 방문 시작 현재 경로: 1 -> 4 -> 2 -> 3 노드 "3" 방문 완료 (백트래킹 후 경로: 1 -> 4 -> 2) 노드 "3"에서 노드 "2"로 백트래킹 노드 "2" 방문 완료 (백트래킹 후 경로: 1 -> 4) 노드 "2"에서 노드 "4"로 백트래킹 노드 "4" 방문 완료 (백트래킹 후 경로: 1) 노드 "4"에서 노드 "1"로 백트래킹 이웃 노드 "5"로 이동 노드 "5" 방문 시작 현재 경로: 1 -> 5 노드 "5" 방문 완료 (백트래킹 후 경로: 1) 노드 "5"에서 노드 "1"로 백트래킹 노드 "1" 방문 완료 (백트래킹 후 경로: 빈 경로) DFS 탐색 완료
하나씩 스태킹을 해나가면서 가장 마지막의 리프 노드에 도달하면 그때부터 백트래킹을 하면서 방문 완료를 실시한다. 이때 인접 노드가 아직 방문하지 않았다면 백트래킹 이후 인접 노드를 방문을 하게 된다.(1 -> 5)
풀어볼 문제
1. 깊이 우선 탐색 순회(몸풀기 문제)
더보기
from collections import defaultdict
# def solution(graph, start) :
# adj_list = defaultdict(list)
# for u, v in graph :
# adj_list[u].append(v)
#
# def dfs(node, visited, result) :
# visited.add(node)
# result.append(node)
#
# for neighbor in adj_list.get(node, []) :
# if neighbor not in visited :
# dfs(neighbor, visited, result)
#
# visited = set()
# res = []
# dfs(start, visited, res)
# return res
def solution(graph, start) :
adj_list = defaultdict(list)
for u, v in graph :
adj_list[u].append(v)
def dfs(node, visited, result) :
stack = []
stack.append(node)
visited.add(node)
result.append(node)
while stack :
current_node = stack.pop()
for neighbor in adj_list.get(current_node, []) :
if neighbor not in visited :
visited.add(neighbor)
result.append(neighbor)
stack.append(neighbor)
return result
visited = set()
res = []
dfs(start, visited, res)
return res
print(solution([['A', 'B'], ['B', 'C'], ['C', 'D'], ['D', 'E']], 'A')) # 반환값 : ['A', 'B', 'C', 'D', 'E']
print(solution([['A', 'B'], ['A', 'C'], ['B', 'D'], ['B', 'E'], ['C', 'F'], ['E', 'F']], 'A')) # 반환값 : ['A', 'B', 'D', 'E', 'F', 'C']파이썬에서는 스택이라는 자료구조가 딱히 존재하지는 않는다. 리스트를 활용하여 스택과 유사하게 동작하도록 만들 수 있기 때문에 DFS를 공부하다보면 스택이라는 자료구조에 대해서 궁금증을 가질 수도 있다.
대체적으로 DFS구현은 재귀로 하는 경우가 많다.
1. 코드가 간결하다. 지금 위에서 살펴봤듯이, 문제의 요구사항이 그렇게 까다롭지 않다면 재귀를 활용하여 문제를 해결하는 것이 시간상 효율적일 수 있다. dfs 함수만 따로 놓고 보자면 6줄 vs 13줄, 2배 이상 차이가 난다.
2. 중복되는 요소를 상당히 줄일 수 있다. 스택으로 구현한 코드를 보면 코드상으로만 봤을 때, visited 집합에 추가하는 동작과 stack에 추가하는 동작, result에 추가하는 동작이 2번 작성되어 있다. 이러한 부분 때문에 코드가 더 간결해지고 직관적이 되다 보니 쉽게 구현할 수 있다고 생각이 든다.
3. 디버깅은 또 다른 문제이다. 간결한 코드는 직관적이어서 알고리즘의 동작을 이해하기 용이하지만, 디버거를 활용하여 상태를 파악하기에는 오히려 스택을 활용한 구현이 더 용이하다. 재귀를 사용하여 디버깅을 하다보면 지금 현재 상태가 어떤 함수로 들어가 있는지 착각하고 있을 때가 많다. 스택은 그럴 가능성이 거의 없기 때문에 디버깅을 활용한다면 스택을 활용하는 것이 더 나은 방법이 될 것이다.
2. 네트워크(프로그래머스)
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
def dfs(computers, visited, node) :
visited[node] = 1
for idx, connected in enumerate(computers[node]) :
if connected and not visited[idx] :
dfs(computers, visited, idx)
def solution(n, computers):
answer = 0
visited = [0] * n
for i in range(n) :
if not visited[i] :
dfs(computers, visited, i)
answer += 1
return answerDFS는 공부를 제대로 하지 않아서 인가 이런 부분에 있어서 참 어렵게 느껴진다.
dfs 함수의 설계부터 보자.
- 현 노드에 방문처리를 한다.
- enumerate 메소드를 활용하여 인접한 컴퓨터의 상태를 확인한다.
- 0번 컴퓨터로 접속을 했다면, 컴퓨터[0][0]은 문제에 주어진 대로 무조건 1일 것이고(그러나 이미 방문처리)
- 컴퓨터[0][1]은 connected = 1 이면서, 방문하지 않은 컴퓨터
- 컴퓨터[0][2]는 connected = 0 이면서, 방문하지 않은 컴퓨터
- 조건문에 따라 연결되어 있으면서, 방문하지 않은 컴퓨터를 찾는다.
- 그리고 다 찾았다면 dfs를 마친다.
이후, solution 함수 설계에서 정답 처리를 진행한다.
- dfs함수를 마치면서, answer += 1 을 한다.
- for 문을 돌면서 n = 3 일때, 0, 1, 2 를 차례로 돌면서 방문하지 않았던 컴퓨터면 dfs를 다시 진입한다.
- 첫 번째 예제의 경우, 0번 컴퓨터 부터 시작. 연결되어 있는 컴퓨터는 0, 1 컴퓨터가 서로 연결되어 있으므로 dfs 진행시 두 컴퓨터에 접속이 발생한다. dfs(0번 컴퓨터 실시) => dfs내에서 0, 1번 두 컴퓨터의 접속이 발생한다.
- 0번 컴퓨터의 dfs를 마친 후, answer += 1을 한다.
- for문을 통하여 1번 컴퓨터로 접속한다.1번 컴퓨터로 접속하나, 이미 방문을 마친 컴퓨터이기 때문에 바로 pass
- for문을 통하여 2번 컴퓨터로 접속을 한다. 방문을 하지 않았기 때문에 dfs(2번컴퓨터) 실시.
- 본인만 연결되어 있기 때문에 본인의 방문표시를 하고 dfs 종료. answer += 1
- answer에 총 2번의 + 1 이 진행되었기 때문에 return 값은 2가 된다.
솔직히 이렇게 풀어놓고 보면 쉽게 따라할 수 있을거 같은데 막상 풀어보려고 문제를 맞닥드리다 보니까 하나도 기억이 안난다. 재귀와 관련해서 어떤 방식으로 풀어나갈지에 대해서 조금 더 고민을 해봐야겠다.
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
def solution(info, edges):
answer = 0
v = [0] * len(info)
v[0] = 1
def dfs(sheep, wolf) :
nonlocal answer
if sheep > wolf :
answer = max(answer, sheep)
else :
return
for prev, curr in edges :
if v[prev] and not v[curr] :
v[curr] = 1
if info[curr] == 0 :
dfs(sheep + 1, wolf)
else :
dfs(sheep, wolf + 1)
v[curr] = 0
dfs(1, 0)
return answer매번 다시 봐도 어렵다고 느껴지는 문제이다. nonlocal 에 대해서는 상위 함수의 지역 변수에 대해 접근하고자 할 때 사용할 수 있다.
역시 이번에도 dfs 함수 먼저 살펴보면 (양의 수, 늑대의 수) 를 변수로 가지는 함수이다. edges의 특징이 [현재 노드, 인접 노드] 로 구성이 되어 있어서 for문에서 튜플로 분리 후 활용하는 방안이다.
- nonlocal로 solution의 answer 변수에 접근한다. 만약 전역변수라면 global로 사용.
- 정답 처리를 하자. 문제에 늑대의 수가 양보다 같거나 많다면 잡아먹힌다고 했으니 그 직전까지는 수행이 가능하다. 그래서 양이 더 많으면 answer 변수를 갱신하고, 늑대가 같거나 많으면 즉시 반환한다. (이 함수를 pop한다.)
- 양의 수가 아직 더 많다면, for문으로 내려와 현재 노드는 지나갔으니 이전 노드로 변경, 인접한 노드를 현재 노드로 변경 하는 로직으로 (이전 노드, 현재 노드)를 edges로 부터 반복해서 들고 올 것이다.
- 이전 노드를 방문한 후 아직 현재 노드를 방문하지 않았다면, 방문 표시를 한다. 그리고 info 배열에 현재 노드가 양(0)인지, 늑대(1)인지 판별한 후, 그 상황에서의 dfs를 재귀적으로 탐색한다.
- 다음 노드가 양일 경우는 계속해서 for문까지 내려와 해당 작업(재귀)를 반복할 것이다.
- 다음 노드가 늑대일 경우, 양과의 수 비교를 통하여 재귀를 계속 진행할지, 팝할지 결정할 것이다.
- 모든 for문을 진행하면, answer 에 최종적으로 가장 많이 양을 보유 했을 때의 값이 남아 있게 될 것이다.
이런 과정을 고민했을 때, 과연 내가 파이썬 코드로 구현이 가능할지에 대해서는 아직 잘 모르겠다.
4. 양궁대회(프로그래머스)
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
이 문제에 대해서는 조금 더 공부한 후에 풀어보겠습니다. 생각보다 많이 어렵네요...
반응형
'코테합 빈출유형 스터디' 카테고리의 다른 글
| [코딩 테스트 합격자 되기 파이썬 - 4주차]시뮬레이션 (0) | 2025.04.27 |
|---|---|
| [코딩 테스트 합격자 되기 파이썬 - 3주차]백트래킹 (0) | 2025.04.20 |
| [코딩 테스트 합격자 되기 파이썬 - 2주차]BFS (0) | 2025.04.13 |