인프런 커뮤니티 질문&답변

위 문제를 파이썬으로 시도했습니다. 몇 주 동안 cpp하다가 파이썬으로 하니 파이썬이 불편함이 있네요..

아래 코드를 실행한 경우, 시간 초과가 떴습니다. 제 생각에는 cpp 내용으로 파이썬 문법으로 그대로 옮겨 적은 거나 마찬가지라고 생각하는데요.

from sys import stdin

def main():
    ret = 0
    ans = []
    n, m = map(int, stdin.readline().split())
    visited = [0 for _ in range(n + 1)]
    tree = [[] for _ in range(n + 1)]

    def dfs(root: int):
        visited[root] = 1
        cnt = 1
        for there in tree[root]:
            if not visited[there]:
                cnt += dfs(there)

        return cnt

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        tree[b].append(a)

    for i in range(1, n):
        cnt = 0
        visited = [0 for _ in range(n + 1)]

        if len(tree[i]) != 0 and not visited[i]:
            cnt = dfs(i)

        if cnt > ret:
            ans.clear()
            ret = cnt
            ans.append(i)
        elif cnt == ret:
            ans.append(i)

    s = ""
    for i in ans:
        s += str(i) + " "

    print(s)



if __name__ == "__main__":
    main()

cpp 쓰다가 파이썬을 쓰니 초기화하는 것도 불편하고, 시간도 많이 걸립니다.

(오랜만에 파이썬으로 다시 짜보면 무슨 느낌일지 궁금해서 시도해봤습니다. 아직은 병행하지 않고, 강의 완주 후에 파이썬으로 해볼 생각입니다. 파이썬을 사용하려는 이유는 파이썬을 사용하는 백엔드 회사에 들어갈려고 하거든요. 백엔드로 취업할려면 자바 스프링하라는 영상을 이미 시청했습니다.)

main 안에다가 변수를 선언하고 그 안에 dfs 함수를 사용해서 클로저 방식으로 사용해봤는데요.

클로저를 사용 안하고 아래 조건문 안에 선언한 후,

if __name__ == "__main__":
    ...
    visited = [0 for _ in range(n + 1)]
    main()

아래 코드처럼 dfs()를 호출하기 전에 visited를 초기화했음에도 불구하고도,

    for i in range(1, n):
        cnt = 0
        visited = [0 for _ in range(n + 1)]

        if len(tree[i]) != 0 and not visited[i]:
            cnt = dfs(i)

dfs()는 main()을 호출하기 전 visited를 인식하여 문제 풀이에 에러가 발생하는 것 같습니다. 일반적으로 변수를 선언한 후, 초기화하면서 변수에 그 값을 담는 방식이라면 파이썬은 이와 달리 변수 이름이 그 값에 라벨링처럼 지시하는 방식이라서 새롭게 변수를 생성하여 다른 변수로 인식하는 것 같습니다.

global 이나 nonlocal 로 선언하여 사용하는 방식이 있으나, 이런 경우 시간 초과가 발생하더군요. 어떻게 해결할 수 있을까요?