* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *
leetcode 207번 ( https://leetcode.com/problems/course-schedule/description/ )
풀이 (교재 참고)
그래프를 DFS로 탐색하면서 순환 구조(cycle)가 있는지 판별하는 문제이다.
예를 들어서 코스 A, B, C가 있을 때 A->B, B->C, C->A 식으로 선수강과목이 있다면 모든 코스를 수강할 수 없다. A, B, C를 그래프의 각 노드로 보았을 때 순환 구조가 있기 때문이다.
이를 확인하기 위해서는 한 과목이 다른 어떤 과목들을 선수강과목으로 갖고 있는지를 정리한 변수가 필요하다.
해시 테이블(hash table)로 구현된 딕셔너리 자료형을 사용해서 key 값으로는 과목을, value 값으로는 해당 과목의 선수강과목 리스트를 갖게 하자.
courses = collections.defaultdict(list)
예를 들어 A과목이 B, C과목을 선수강과목으로 갖고 있다면 다음과 같이 표현할 수 있다.
courses[A] = [B, C]
이후 A과목의 선수강과목인 B, C 과목에 대해서 DFS 탐색을 하고, 또 B과목과 C과목의 선수강과목들에 대해서 DFS 탐색을 하고... 이런 식으로 재귀적으로 DFS 탐색을 하는 과정에서 중간에 A나 B, C과목이 중복으로 탐색된다면 그래프 내에 순환구조가 있는 것이므로 False를 리턴한다. 전혀 중복이 없다면 True를 리턴한다.
중첩 함수 dfs()를 선언해서 cycle이 있으면 False, 없으면 True를 리턴하도록 한다.
이때 dfs()는 개별 노드를 매개변수로 받고, 한 노드와 연결된 다른 노드들에 대해서 DFS 탐색을 모두 실행했을 때 cycle이 전부 없다면 True, 하나라도 있다면 False를 리턴한다.
def dfs(node):
if cycle:
return False
else:
return True
순환 구조를 탐색하기 위해서는 현재 탐색중인 DFS 경로에 어떤 노드들이 있는지를 계속 저장하고, 새 노드를 추가할 때마다 탐색 중인 DFS 경로에 이미 있는 노드와 겹치지 않는지 확인하면 된다.
탐색하는 노드들은 순환이 존재하지 않는 한 전부 다른 노드들이므로 set()을 사용해서 집합 형태로 선언해도 된다.
traced = set()
traced.add(node)
dfs(node)
traced.remove(node)
그리고 한 경로의 DFS 탐색이 끝나면 해당 노드를 traced에서 제거해야 한다. 제거하지 않으면 이후에 다른 경로로 DFS 탐색을 할 때, 전혀 다른 경로에서 탐색했던 노드를 cycle로 잘못 판단할 수 있다.
그런데 이 경우 DFS 탐색을 여러 번 하면서 이미 탐색했던 노드를 불필요하게 여러 번 탐색할 수 있다. 따라서 이미 탐색한 노드는 더 이상 DFS 탐색을 하지 않고, True(cycle 없음)를 리턴해 주면 탐색 시간을 줄일 수 있다.
visited = set()
dfs(node)
visited.add(node)
위에서 선언한 traced와 visited를 사용해서, 만약 노드가 traced에 있다면 탐색 중인 경로에 있었던 것이므로 순환 구조가 있는 것이다. 이 경우 False를 리턴한다.
만약 노드가 visited에 있다면, 이미 해당 노드에 대해선 DFS 탐색이 완료된 노드이므로 더 이상 탐색을 할 필요가 없다. 그러므로 True를 리턴한다.
def dfs(node):
if node in traced:
return False
if node in visited:
return True
확인을 한 이후 해당 노드에 대해서 DFS 탐색을 시작한다.
우선 traced 변수에 노드를 추가하고, 해당 노드의 모든 선수강과목들에 대해서 DFS 탐색을 한다. 하나라도 False가 리턴되었다면(cycle이 있다면) False를 리턴한다.
traced.add(node)
for c in courses[node]:
if not dfs(c):
return False
전부 True가 리턴되었다면 해당 노드에 대해서는 순환구조가 없는 것이므로 더 이상 경로를 탐색하지 않을 것이기 때문에 traced 변수에서 해당 노드를 제거한다.
또한 앞으로 해당 노드는 다시 탐색할 필요가 없기 떄문에 visited 변수에다가 해당 노드를 추가한다.
traced.remove(node)
visited.add(node)
dfs() 함수를 이렇게 구현한 뒤, for loop로 딕셔너리 courses를 순회하면서 선수강과목이 있는 모든 노드에 대해서 DFS 탐색을 실행하면 된다.
for elem in list(courses):
if not dfs(elem):
return False
return True
+ 부록
마지막 for loop로 순회하는 부분에서, 딕셔너리 변수를 그대로 쓰지 않고 list()로 한 번 묶은 이유는 무엇일까?
딕셔너리 변수를 그대로 사용할 경우, 'iteration 중간에 딕셔너리의 크기가 변경되었다'는 오류가 발생한다. 그 이유는 dict()이 아니라 collections.defaultdict()으로 딕셔너리를 선언했기 때문이다.
collections.defaultdict()은 dict()와 달리 조회하는 key값이 없을 경우 오류를 리턴하지 않고 key-value 쌍을 기본으로 생성한다. 그러므로 딕셔너리 값이 변경되기 때문에 에러가 발생한 것이다.
list()를 사용하면 id가 다른 딕셔너리의 복사본을 만들 수 있고, courses는 변경되지만 list(courses)는 원본이 아닌 복사본이라 변경되지 않으므로 에러가 발생하지 않는다.
'알고리즘' 카테고리의 다른 글
| ch13-2(leetcode 787). K 경유지 내 가장 저렴한 항공권 (0) | 2023.02.11 |
|---|---|
| ch13-1(leetcode 743). 네트워크 딜레이 타임 (0) | 2023.01.24 |
| ch12-7(leetcode 332). 일정 재구성 (0) | 2023.01.19 |
| ch12-6(leetcode 78). 부분 집합 (0) | 2023.01.19 |
| ch12-5(leetcode 39). 조합의 합 (0) | 2023.01.18 |
