글 읽기 - 파이썬 런타임 에러 궁금합니다...

ad1259 3년 전 0

파이썬 코드입니다.

런타임 에러가 나는데 어떤 반례가 있는지 궁금해요..

어떤 조건을 빼먹었는지,

혹은 코딩을 잘못한 구간이 있는지 모르겠어요!

ps : dfs,bfs는 기본이라는데 너무 어렵네요 ㅠ

cnt = 0
lst = []
def dfs(x,y) :
    global cnt
    matrix[x][y] = 0
    cnt +=1
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    for i in range(4) :
        ddx = x + dx[i]
        ddy = y + dy[i]
        if ddx< 0 or ddx>=m or ddy<0 or ddy>=n :
            continue
        if matrix[ddx][ddy] == 1 :
            dfs(ddx,ddy)
    
t = int(input())
for _ in range(t) :
    lst = []
    m,n,k = list(map(int,input().split()))
    matrix = [[0]*(n) for _ in range(m)]
    for i in range(k) :
        x,y = map(int,input().split())
        matrix[x][y] = 1
    for i in range(m) :
        for j in range(n) :
            if matrix[i][j] == 1 :
                cnt = 0
                dfs(i,j)
                lst.append(cnt)
    print(len(lst))

liza0525 3년 전 1

dfs를 재귀로 짜셨기 때문에 나온 거 같습니다.
왜냐면 m = 50, n = 50, k = 2500일 때
재귀 깊이가 2500 이상이 되기 때문입니다.
파이썬에서는 재귀 제한이 1000까지 밖에 안됩니다.
재귀 제한 횟수가 넘어가면 런타임에러가 나와요.
따라서 스택으로 푸시거나

import sys
sys.setrecursionlimit(10 ** 4)

위 코드를 적으셔서 재귀 제한 횟수를 늘리시면 됩니다.
(재귀 제한 횟수를 늘리면 메모리가 늘어나기 때문에 적당히 늘려주시면 됩니다.
꼭 10 ** 4가 아니어도 되고 2500보다 크게 하시면 될 것 같습니다.)

ad1259 3년 전 0

와... 재귀 제한 횟수 늘리는 코드 꿀팁이네요

스택으로 푸는 방법으로도 연습해봐야겠네요

감사합니다

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

문제

문제

출처

ICPC

파이썬 런타임 에러 궁금합니다...

ad1259 3년 전 0

liza0525 3년 전 1

ad1259 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말