글 읽기 - 파이썬 런타임 오류

heumsi 5년 전 0

안녕하세요.

질문글에 파이썬을 푸신 분이 없어서 답답하네요 ㅠ

하루종일 고민하다가, 올리게 됩니다...

코드는 아래와 같고, 시간복잡도는 O(n) 예상하는데, 어디서 런타임 오류가 발생되는걸까요??

import sys
sys.setrecursionlimit(10*8)

def dfs(idx, value, visited, total_visited):

    if idx in total_visited:
        # 현재 인덱스가 방문된 적이 있다면,
        # 이후 dfs 순회가 이미 끝난 것이므로, 더 탐색하지 않고 종료.
        return True, None

    visited.add(idx)
    total_visited.add(idx)

    if value in visited:
        # 다음 방문 인덱스(value)가 이미 방문한 적이 있다면, 사이클을 발견한 것임.
        # 다음 방문 인덱스(value)가 사이클 시작점. 
        global team
        team += 1
        return (idx == value), value

    # 사이클을 발견할 떄까지 dfs를 진행하고,
    # 찾았을 때, 사이클 시작 인덱스(start_index)와,
    # back하면서 현재 사이클 내부인지(is_cycle)이 체크.
    is_cycle, start_idx = dfs(value, students[value], visited, total_visited)
    if is_cycle == False:
        # back하면서 아직 사이클 내부라면, 현재 인덱스는 팀에 소속된 것.
        team += 1
        if idx == start_idx:
            # back하면서 현재 인덱스가 사이클 시작점이라면,
            # 이후 back하며 방문되는 인덱스는 모두 팀에 소속되지 않음.
            is_cycle = True

    return is_cycle, start_idx


tc = int(sys.stdin.readline())
for t in range(tc):
    n = int(sys.stdin.readline())
    students = list(map(int, sys.stdin.readline().split()))
    students = [x-1 for x in students]
    team = 0
    visited = set()

    for idx, value in enumerate(students):
        if idx in visited:
            continue
        dfs(idx, value, set(), visited)
    
    # 팀에 속하지 않은 사람 수 = 전체 인원 수 - 팀에 소속된 사람 수
    print(n - team)

mike1201 5년 전 1

저도 83% 쯤에서 런타임 오류가 나는데 이거 메모리나 아니면 재귀 depth 문제 인 것 같은데... 혹시 해결하셨나요??

heumsi 5년 전 0

저의 경우 좀 허무했는데요 ㅠ 말씀하신대로 뎁스 문제였어요.

위 코드 보시면 상단에 sys.setrecursionlimit(10*8) 로되어있잖아요

10*8 이 아니라 10**8 로 둬야합니다... 오타가 문제였어요 ㅋㅋㅋ

mike1201 5년 전 0

저 바로 위에 질문글 썼는데 혹시 봐주실수있나요 ㅜㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 런타임 오류

heumsi 5년 전 0

mike1201 5년 전 1

heumsi 5년 전 0

mike1201 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말