문제
입력
2, [[1,0]]출력
True입력
2, [[1,0],[0,1]]출력
False코드
visited 없을 때
from typing import List
import collections
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = collections.defaultdict(list)
for x, y in prerequisites:
graph[x].append(y)
traced = set()
def dfs(i):
if i in traced:
return False
traced.add(i)
for y in graph[i]:
if not dfs(y):
return False
traced.remove(i)
return True
for x in list(graph):
if not dfs(x):
return False
return Truevisited 있을 때
from typing import List
import collections
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = collections.defaultdict(list)
for x, y in prerequisites:
graph[x].append(y)
traced = set()
visited = set()
def dfs(i):
if i in traced:
return False
if i in visited:
return True
traced.add(i)
for y in graph[i]:
if not dfs(y):
return False
traced.remove(i)
visited.add(i)
return True
for x in list(graph):
if not dfs(x):
return False
return True풀이
문제에서의 코스는 첫 번째 테스트 케이스를 예로 들자면 0과 1 2개로 말할 수 있다. 풀이에서는 코스의 개수는 필요없다. 이 문제는 그래프가 순환 구조인지를 판별하는 문제로 풀이할 수 있다. 순환 구조라면 계속 뱅글뱅글 맴돌게 될 것이고, 해당 코스는 처리할 수 없기 때문이다.
graph = collections.defaultdict(list)
for x, y in prerequisites:
graph[x].append(y)페어들의 목록인 prerequisites 변수를 풀어서 그래프로 표현한다.
traced = set()
...
for x in graph:
if not dfs(x):
return False
return True순환 구조를 판별하기 위해 앞서 이미 방문했던 노드를 traced 변수에 저장한다. 이미 방문했던 곳을 중복 방문하게 된다면 순환 구조로 간주할 수 있고, 이 경우 False를 리턴하고 종료한다.
def dfs(i):
if i in traced:
return False
traced.add(i)
for y in graph[i]:
if not dfs(y):
return False
traced.remove(i)
return True해당 노드를 이용한 모든 탐색이 끝나게 된다면 traced.remove(i)로 방문했던 내역을 반드시 삭제한다. 그렇지 않으면 형제노드가 방문한 노드까지 남게 되어, 자식 노드 입장에서는 순환이 아닌데 순환이라고 잘못 판단할 수 있기 때문이다.
지금까지의 visted가 없는 코드에서 visted를 추가하여 완전히 탐색이 끝난 코스를 visted에 추가해 둔다면 dfs 바깥쪽 for문에서 만약 방문을 했다면 바로 True를 반환하기에 시간을 절약할 수 있다. 즉 [0,1], [0,2], [1,2]에서 dfs 바깥쪽에 0이 돌아가면 0, 1, 2 다 방문하므로 1이 돌아갈 때 if i in visited에서 걸려 바로 True를 반환하게 된다.
헷갈렸던 부분
[0,1], [0,2], [1,2]가 들어올 때를 생각해보자. (visited가 적용안된 코드에서)
처음 dfs(0)이 호출되고 traced에 0이 들어간다. 이후 for문에서 1, 2가 돌아가게 된다. 그러면 dfs(1)이 호출된다.
dfs(1)이 호출되고 traced에 0, 1이 들어간다. 이후 for문에서 2 한번만 돌아가고 그러면 dfs(2)가 호출된다.
dfs(2)가 호출되고 traced에 0, 1, 2가 들어간다. 그리고 for문은 돌지 않게 되고, 현재 i가 traced에서 삭제되어 traced는 0, 1이 된다. 이후 dfs(2)는 True를 반환하고 종료한다.
그러면 dfs(1)로 다시 백트래킹이 되고, if not dfs(2)인데 if not True이므로 if문 안으로 들어가지 않는다. 이 후 for문도 한번만 돌아가므로 빠져 나와 현재의 i가 traced에서 삭제되어 traced는 0이된다. 이후 dfs(1)은 True를 반환하고 종료한다.
그러면 dfs(0)으로 백트래킹이 되고, if not dfs(1)인데 if not True이므로 if문 안으로 들어가지 않는다. 여기서는 for문이 1, 2 두번 돌아가므로 다음 for문 2가 돌아가게 되고, dfs(2)가 호출된다. 근데 이 때 traced.remove(i)로 방문했던 내역을 삭제 안했더라면 2는 traced안에 들어있게 되어 False를 리턴해서 순환구조로 착각하게 된다. 그래서 traced.remove(i)가 필요하다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]