글 읽기 - python으로 시간초과 문제

trevor0513 5년 전 0

안녕하세요. 원숭이가 말이 되고싶은 문제를 풀다가 시간초과가 발생해서 질문 올립니다 ㅠㅠ...

50%에서 시간 초과가 발생하는데 이것보다 더 최적화 할 수 있는 방안이 생각이 안나네요. 현명하신분들의 조언을 좀 듣고싶습니다..

대부분의 코드는 읽기 쉬울것같습니다만,

cnt는 이동 횟수를 의미하며,

visited는 방문여부를 저장하는데 기본적으로 방문하지 않았으면 -1을 저장하고있고

방문을 했으면 남은 K값이 저장되어있습니다.

지금 온 위치에서 더 많은 K로 이 곳을 통과한 과거 경험이 있으면 queue에 추가하는건 의미가 없어서 추가하지 않습니다.

우선순위 큐를 이용해서 cnt가 적은 순서대로 pop합니다.

고수님들 더 최적화를 할 수 있는 방법좀 알려주세요 ㅠㅠ

import sys
from heapq import heappop, heappush
r = lambda: sys.stdin.readline()

def iszero(cur_y, cur_x):
    if cur_y>=0 and cur_x>=0 and cur_y<y and cur_x<x:
        if mat[cur_y][cur_x] == 0:
            return True
    return False

monkey_move_x = [0,0,1,-1]
monkey_move_y = [1,-1,0,0]
hours_move_x = [1, 2, 2, 1, -1, -2, -2, -1]
hours_move_y = [-2, -1, 1, 2, 2, 1, -1, -2]
def move(cnt, cur_y, cur_x, isHouse, cur_K):
    if isHouse:
        move_y, move_x = hours_move_y, hours_move_x
        next_k = cur_K - 1
    else:
        move_y, move_x = monkey_move_y, monkey_move_x
        next_k = cur_K
    for m_y, m_x in zip(move_y, move_x):
        next_y = m_y + cur_y
        next_x = m_x + cur_x
        if iszero(next_y, next_x):
            if visited[next_y][next_x] == -1 or visited[next_y][next_x] < next_k:
                visited[next_y][next_x] = next_k
                heappush(q, [cnt+1, [next_y, next_x, next_k]])
    return None

def main():
    global x, y, visited, mat, q
    K = int(r().strip())
    x, y = [int(i) for i in r().split()]
    mat = []
    for _ in range(y):
        mat.append([int(i)for i in r().split()])

    visited = [[-1 for _ in range(x)] for _ in range(y)]
    visited[0][0] = K
    q = []
    heappush(q, [0, [0, 0, K]]) #[y,x,K]

    while q:
        cnt, [cur_y, cur_x, cur_K] = heappop(q)
        if cur_y == y-1 and cur_x == x-1:
            return cnt

        #상하좌우
        move(cnt, cur_y, cur_x, False, cur_K)

        #말
        if cur_K > 0:
            move(cnt, cur_y, cur_x, True, cur_K)
    return -1

if __name__ == '__main__':
    print(main())

jh05013 5년 전 1

python과 똑같은데 훨씬 빠른 pypy로 제출해 보세요.

가까스로 통과는 되지만, 몇 가지 비효율적인 부분이 있습니다. [0, [0, 0, K]]보다 tuple (0, 0, 0, K)가 더 가벼울 것이고, 다익스트라 알고리즘 말고 BFS로 더 빠르게 풀 수 있습니다.

trevor0513 5년 전 0

jh05013 님 감사합니다 ㅠㅠ pypy3로 제출하니까 통과하네요.

다른 방법으로도 풀어볼게요!

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

문제

문제

출처

ICPC

python으로 시간초과 문제

trevor0513 5년 전 0

jh05013 5년 전 1

trevor0513 5년 전 0

jh05013 님 감사합니다 ㅠㅠ pypy3로 제출하니까 통과하네요.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말