[항해99] 99클럽 코테 스터디 11일차 TIL + DFS 백준 25195

99클럽 코테 스터디 11일차 TIL + DFS 백준 25195

오늘의 학습 키워드

• DFS
• 백준 25195
• Yes or yes

공부한 내용

1. DFS

• DFS를 활용해서 정점까지의 경로 중에 곰곰이 팬을 피할 수 있는지 확인하는 것

def DFS(v):
    global visited, graph, answer
    if v in fans:  # 현재 노드에 팬이 있으면 return
        return 

    if not graph[v]:  # 리프 노드에 도달했고 팬을 만나지 않았다면
        answer = True  # 팬을 피할 수 있는 경로 발견
        return 

    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            DFS(i)
    visited[v] = False  # 백트래킹

2. 백트래킹

• visited = [False]로 방문 체크를 해제하여 다른 경로 탐색에도 활용할 수 있도록 함
• 이를 통해 모든 가능한 경로를 확인할 수 있음

3. 전역 변수 활용

• global을 활용해 함수 내에서 변수를 활용
• visited, graph, answer를 전역 변수로 활용

4. 재귀 깊이 제한

• Runtimeerror를 피하기 위한 방법

  import sys
  sys.setrecursionlimit(10**6)

오늘의 회고

• 전역 변수로 answer를 설정하지 않아서 오류가 발생했었다. answer를 잘못 설정하여 발생하는 오류라는 것을 깨닫는데 꽤 오래걸렸음.
• DFS에서 백트래킹을 활용해서 모든 경로도 탐색할 수 있다는 것을 새롭게 알 수 있었음.
• 재귀 깊이 제한을 sys.setrecursionlimit()으로 제한을 늘려 해결