출처 : 파이썬 알고리즘 인터뷰

주말 잘~쉬고 왔습니다

는 사실 맥도날드에서 버거 만들고 옴..

벌써 dfs 깨부수기 7일차...!!!

7일이나 지났는데 과연 깨부수었는가?

-> 손날로 두부정도는 깨부술 수 있을 실력됨..예..

근데 3회독 하면 훨씬 괜찮을듯?

진짜 신기하게 저번에 그냥 지나쳤던 부분들까지 이해가 조금씩 되면서

다른 문제에도 적용할 수 있게 되는 것 같다.

아니 어떻게 풀어야돼 -> 음 이렇게 풀면 대충 각 나오겠다

이정도까지는 가능

오늘의 문제

leetcode 207.Course Schedule

이 문제는 n개의 노드를 방문하는데, 1을 끝내려면 0을 끝내야되고 어쩌구...라고 설명하고 있지만 사실 순환구조가 있는지를 판별하는 문제라고 생각했다.

생각의 흐름

0을 끝내려면 1을 끝내야되고 1을 끝내려면 0을 끝내야된다라..?

-> 그래프로 그려보자

-> 순환 구조가 생기겠구나

-> 순환 구조가 생기면 False를 return 하면 되겠구나

순환구조는 어떻게 판별하지

-> 이미 방문한 노드들을 기억해두면 되겠다

접근 1

그래프로 바꿔서 저장

graph = collections.defaultdict(list)

for start, end in prerequisites:
  graph[start].append(end)

이제 그래프로 바꾸는거 쯤은 눈감고 해요

접근 2

dfs 설계

1. 탐색하고자 하는 곳을 이미 탐색했던 기억이 있으면 True
2. 순환구조면 False
3. 탐색 후에는 기억하기

def dfs(start):
  # 이미 탐색?
  if start in visited: return True
  # 순환구조?
  if start in traced: return False

	traced.add(start)
  for end in graph[start]:
    if not dfs(end):
      return False
  traced.remove(start)
  
  visited.add(start)
  return True

key : traced로 순환구조를 추적할 때

재귀로 호출되는 dfs에만 영향을 주기 위해

for문 밖에서 add해주었다가 for문 끝나면 지워주는 구조를 이해하는게 중요하다

최종 코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
      graph = collections.defaultdict(list)
      visited = set()
      traced = set()
      
      for start, end in prerequisites:
        graph[start].append(end)
        
      def dfs(start):
        if start in visited: return True
      	if start in traced: return False
      
      	traced.add(start)
      	for i in graph[start]:
          if not dfs(i):
            return False
        traced.remove(start)
        
        visited.add(start)
    
    
    	for i in list(graph):
        if not dfs(i):
          return False
      
      return True