글 읽기 - 맞긴했는데 이해가안갑니다(시간초과문제)

qkrwnstns52 3년 전 0

왜 이동방향 순서에 따라 시간초과냐 성공이냐 여부가 갈리는건가요???,..

###첫번째 코드###

from sys import stdin
from collections import deque
input = stdin.readline

n, m, k = map(int, input().split())
a = [list(input()) for _ in range(n)]
dist = [[[0]*(k+1) for _ in range(m)] for _ in range(n)]
dx = [-1, 0, 1, 0]    
dy = [0, 1, 0, -1]    # 두번째 코드와 다른부분

def bfs():
    q = deque()
    q.append((0, 0, 0))
    dist[0][0][0] = 1
    while q:
        x, y, z = q.popleft()
        if x == n-1 and y == m-1:
            return dist[n-1][m-1][z]
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if -1 < nx < n and -1 <ny < m:
                if dist[nx][ny][z]:
                    continue
                if a[nx][ny] == '0':
                    dist[nx][ny][z] = dist[x][y][z] + 1
                    q.append((nx, ny, z))
                if a[nx][ny] == '1' and z+1 <= k:
                    dist[nx][ny][z+1] = dist[x][y][z] + 1
                    q.append((nx, ny, z+1))
    return -1

print(bfs())




###두번째 코드###


from sys import stdin
from collections import deque
input = stdin.readline

n, m, k = map(int, input().split())
a = [list(input()) for _ in range(n)]
dist = [[[0]*(k+1) for _ in range(m)] for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]  #첫번째 코드와 다른 부분

def bfs():
    q = deque()
    q.append((0, 0, 0))
    dist[0][0][0] = 1
    while q:
        x, y, z = q.popleft()
        if x == n-1 and y == m-1:
            return dist[n-1][m-1][z]
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if -1 < nx < n and -1 <ny < m:
                if dist[nx][ny][z]:
                    continue
                if a[nx][ny] == '0':
                    dist[nx][ny][z] = dist[x][y][z] + 1
                    q.append((nx, ny, z))
                if a[nx][ny] == '1' and z+1 <= k:
                    dist[nx][ny][z+1] = dist[x][y][z] + 1
                    q.append((nx, ny, z+1))
    return -1

print(bfs())

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

문제

문제

출처

ICPC

맞긴했는데 이해가안갑니다(시간초과문제)

qkrwnstns52 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말