글 읽기 - [파이썬] 시간초과

care9000 4년 전 0

파이썬 시간초과 이유를 모르겠습니다 ㅠㅠ

def Moving_pipe(x, y, pipe_type):
    global cnt
    if pipe_type == 1:
        for move in range(2):
            x_tem = x + pipe_1_x[move]
            y_tem = y + pipe_1_y[move]
            if ispass(x_tem, y_tem):
                if move == 1:
                    if house_map[x_tem - 1][y_tem] == 0 and house_map[x_tem][y_tem - 1] == 0:
                        if x_tem == N - 1 and y_tem == N - 1:
                            cnt += 1
                        else:
                            Moving_pipe(x_tem, y_tem, move + 1)

                else:
                    if x_tem == N - 1 and y_tem == N - 1:
                        cnt += 1
                    else:
                        Moving_pipe(x_tem, y_tem, move + 1)
    elif pipe_type == 2:
        for move in range(3):
            x_tem = x + pipe_2_x[move]
            y_tem = y + pipe_2_y[move]
            if ispass(x_tem, y_tem):
                if move == 1:
                    if house_map[x_tem - 1][y_tem] == 0 and house_map[x_tem][y_tem - 1] == 0:
                        if x_tem == N - 1 and y_tem == N - 1:
                            cnt += 1
                        else:
                            Moving_pipe(x_tem, y_tem, move + 1)
                else:
                    if x_tem == N - 1 and y_tem == N - 1:
                        cnt += 1
                    else:
                        Moving_pipe(x_tem, y_tem, move + 1)

    else:
        for move in range(2):
            x_tem = x + pipe_3_x[move]
            y_tem = y + pipe_3_y[move]
            if ispass(x_tem, y_tem):
                if move == 0:
                    if house_map[x_tem - 1][y_tem] == 0 and house_map[x_tem][y_tem - 1] == 0:
                        if x_tem == N - 1 and y_tem == N - 1:
                            cnt += 1
                        else:
                            Moving_pipe(x_tem, y_tem, move + 2)
                else:
                    if x_tem == N - 1 and y_tem == N - 1:
                        cnt += 1
                    else:
                        Moving_pipe(x_tem, y_tem, move + 2)


def ispass(x, y):
    if -1 < x < N and -1 < y < N and house_map[x][y] == 0:
        return True
    return False




# 가로 파이프 다음거
pipe_1_x = [0, 1]
pipe_1_y = [1, 1]

# 세로 파이프 다음거
pipe_3_x = [1, 1]
pipe_3_y = [1, 0]

# 대각선 파이프 다음거
pipe_2_x = [0, 1, 1]
pipe_2_y = [1, 1, 0]


N = int(input())
house_map = [list(map(int, input().split())) for _ in range(N)]

cnt = 0
Moving_pipe(0, 1, 1)
print(cnt)

djm03178 4년 전 1

이유는 간단합니다. 파이썬이 너무 느리기 때문입니다.

이 문제는 원래 완전탐색을 의도하고 만들어진 문제이고, 이 때문에 방법의 최대 횟수에 제한이 따로 걸려있는 것이지만, https://www.acmicpc.net/board/... 와 같이 이 제한은 크게 의미가 없습니다. 빠른 언어로도 완전탐색을 효율적으로 구현하지 않으면 시간 초과에 걸리고는 하는데, 느린 언어로는 상당히 어려워집니다.

파이썬 + 완전탐색을 고수하시려면 코드에서 조금이라도 시간을 걸리게 만들 수 있는 요소는 최대한 다 제거하셔야 하고, Python 3 대신 PyPy3를 써야만 합니다. 그래도 통과는 보장할 수 없습니다. 안전한 방법은 완전탐색 대신 동적 계획법을 사용하거나, 더 빠른 다른 언어를 사용하는 것입니다.

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

문제

문제

출처

ICPC

[파이썬] 시간초과

care9000 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말