글 읽기 - (Python3) 43%에서 계속 시간 초과가 납니다...

minjea917 1년 전 1

이동을 하려는 곳이 더 적은 말의 움직임으로 갔다면 이동하지 않는 식으로 코드를 짰습니다.

3차원 배열로 풀이도 있지만, 제가 볼 땐 충분히 2차원 배열로 풀 수 있을 거 같습니다.

어느 부분이 문제인지 궁금합니다.

from collections import deque


def outRange(thereX, thereY, W, H):
    if 0 <= thereX <= W and 0 <= thereY <= H:
        return False
    return True


K = int(input())
W, H = map(int, input().split())
board = [input().split() for h in range(H)]
visit = [[-1 for w in range(W)] for h in range(H)]
W, H = W - 1, H - 1

Mir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
Hir = [[-2, 1], [-2, -1], [-1, 2], [-1, -2], [1, 2], [1, -2], [2, 1], [2, -1]]
answer = -1

q = deque([(0, 0, 0, K)])
while q:
    hereX, hereY, hereC, hereK = q.popleft()
    if hereX == W and hereY == H:
        answer = hereC
        break

    if hereK >= 1:
        for h in Hir:
            thereX, thereY = hereX + h[0], hereY + h[1]
            if outRange(thereX, thereY, W, H) or board[thereY][thereX] == '1':
                continue
            if visit[thereY][thereX] < hereK - 1:
                visit[thereY][thereX] = hereK - 1
                q.append((thereX, thereY, hereC + 1, hereK - 1))

    for m in Mir:
        thereX, thereY = hereX + m[0], hereY + m[1]
        if outRange(thereX, thereY, W, H) or board[thereY][thereX] == '1':
            continue
        if visit[thereY][thereX] < hereK:
            visit[thereY][thereX] = hereK
            q.append((thereX, thereY, hereC + 1, hereK))

print(answer)

minjea917 1년 전 0

되게 이상항 부분에서 에러가 났네요

범위 이탈 체크해주는 outRange함수의 내용을 그냥 if에 때려박으니 통과했습니다.

그리고 이 코드 그대로 PyPy3으로 돌리니 통과하네요

다 풀어놓고 이상항 부분에서 삽질만 엄청 한 문제;;

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

문제

문제

출처

ICPC

(Python3) 43%에서 계속 시간 초과가 납니다...

minjea917 1년 전 1

minjea917 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말