글 읽기 - 46%에서 시간초과가 나옵니다..

zxaq15 4년 전 0

시간초과에러가 나오는데 어디부분이 잘못됬는지를 모르겠습니다!

from collections import deque


def find_min():
    cnt = 0
    while queue:
        # print(f"{cnt}: {queue}")
        cnt += 1
        x, y, jump = queue.popleft()
        if x == h - 1 and y == w - 1:  # index는 0부터 시작이니까 1 빼줘야함
            return visited[x][y][jump]
        move_around(x, y, jump)
        if jump < k:
            move_diagonal(x, y, jump)
    return -1  # 도착못하는경우면 문제조건에 따라 -1을 리턴


def move_around(x, y, jump):
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    for i in range(4):
        nx, ny, nz = x + dx[i], y + dy[i], jump
        if 0 <= nx < h and 0 <= ny < w:  # matrix 인덱스 범위에 맞을경우에만 통과
            if matrix[nx][ny] != 1:  # 가려는 곳에 장애물이 없을 경우
                if not visited[nx][ny][nz]:
                    visited[nx][ny][nz] = visited[x][y][jump] + 1
                    queue.append((nx, ny, nz))


def move_diagonal(x, y, jump):
    dx = [-2, -1, 1, 2]
    dy = [-1, 1, -2, 2, -2, 2, -1, 1]
    nx, ny, nz = x, y, jump + 1  # 미리 초기화로 선언해줘야 두번째 if문에서 변수로써 사용 가능, nz는 본래들어온 jump + 1을 해줘야 다음걸 탐색하게됨
    for i in range(8):
        if 0 <= i < 2:
            nx, ny = x + dx[0], y + dy[i]
        elif 2 <= i < 4:
            nx, ny = x + dx[1], y + dy[i]
        elif 4 <= i < 6:
            nx, ny = x + dx[2], y + dy[i]
        elif 6 <= i < 8:
            nx, ny = x + dx[3], y + dy[i]

        if 0 <= nx < h and 0 <= ny < w:  # matrix 인덱스 범위에 맞을경우에만 통과
            if nz <= k and matrix[nx][ny] != 1:  # 여기서는 nz값이 k랑 같아도 된다.
                if not visited[nx][ny][nz]:
                    visited[nx][ny][nz] = visited[x][y][jump] + 1
                    queue.append((nx, ny, nz))


k = int(input())
w, h = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(h)]
visited = [[[0]*(k+1) for _ in range(w)] for _ in range(h)]  # ex) visited[3][4][1] = 4이면 (3,4)좌표까지 점프를 1번썼고 최소거리가 4
queue = deque([(0, 0, 0)])  # 문제에서 (0, 0)이 시작점, 세번째 0은 jump를 의미
print(find_min())

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

문제

문제

출처

ICPC

46%에서 시간초과가 나옵니다..

zxaq15 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말