파이썬 백준 2617 구슬 찾기

import sys input = sys.stdin.readline sys.setrecursionlimit(10**8) Vn, En = map(int, input().split()) V = [[] for i in range(Vn + 1)] U = [[] for i in range(Vn + 1)] for i in range(En) :     big, small = map(int, input().split())     V[big].append(small)     U[small].append(big) def DFS(dic, now) :     gone[now] = True     for next in dic[now] :         if not gone[next] :             DFS(dic, next)             count = 0 for i in range(1, Vn + 1) :     gone = [False for i in range(Vn + 1)]     DFS(V, i)     if sum(gone) - 1 >= Vn // 2 + 1 :         count = count + 1     else :          gone = [False for i in range(Vn + 1)]         DFS(U, i)         if sum(gone) - 1 >= Vn // 2 + 1 :             count = count + 1 print(count)

대소에 따라 부모자식관계를 기록할 V, V와 반대 방향으로 기록할 U를 인풋에 따라 작성한다.

아직 안간 점에 방문기록을 남기며 재귀하는 DFS를 정의한다.

모든 점에 대해 for문을 돌리며 DFS를 U,V에 대해 실행해 조건에 맞는 점을 세 출력한다.

난이도 상의 DFS 문제라 이렇게 U, V 만들고 2배의 메모리 2배의 연산으로 풀면 당연히 안될 것 같아서 뭔가 하나의 DFS 안에서 잘 셀 방법을 고민했는데, 그냥 해서 되니까 당황스럽다...