글 읽기 - pypy3, python3 차이점 관련 질문(파이썬 dfs)

yb92 3년 전 1

안녕하세요.

파이썬으로 재귀 DFS를 이용하여 문제를 풀어보았습니다.

처음에 pypy3로 채점시 런타임 에러가 발생해서 재귀 깊이를 늘려주어 해결하고자 했는데 메모리 초과가 발생하였고,

동일 코드를 python3로 제출하였더니 통과되었습니다. pypy3로는 메모리 제한에 걸리는데 python3로는 통과가 되는 이유 설명 부탁드립니다.

추가로, 재귀함수 깊이 제한이 python보다 pypy가 널널한 것이 맞는지와 DFS를 구현할 때 재귀와 stack 중에 어느 것이 실행 속도 등에서 유리한지 알려주시면 감사하겠습니다!

from sys import setrecursionlimit
setrecursionlimit(1000000)


def is_pass(yy, xx):
    if 0 <= yy < n and 0 <= xx < m and cabbage_map[yy][xx] == 1:
        return True
    else:
        return False


def dfs(now_y, now_x):
    for my, mx in zip(dy, dx):
        new_y = now_y + my
        new_x = now_x + mx
        if is_pass(new_y, new_x) and not visited[new_y][new_x]:
            visited[new_y][new_x] = True
            dfs(new_y, new_x)


if __name__ == '__main__':
    t = int(input())

    for tc in range(1, t + 1):
        m, n, k = map(int, input().split())
        cabbage_map = [[0] * m for _ in range(n)]
        for _ in range(k):
            x, y = map(int, input().split())
            cabbage_map[y][x] = 1

        dy = [-1, 1, 0, 0]
        dx = [0, 0, -1, 1]

        visited = [[False] * m for _ in range(n)]
        ans = 0
        for y in range(n):
            for x in range(m):
                if cabbage_map[y][x] == 1 and not visited[y][x]:
                    visited[y][x] = True
                    dfs(y, x)
                    ans += 1

        print(ans)

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

문제

문제

출처

ICPC

pypy3, python3 차이점 관련 질문(파이썬 dfs)

yb92 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말