글 읽기 - 두 코드의 걸린시간 차이가 발생하는 이유를 잘 모르겠습니다

sibaek 1년 전 0

첨부된 코드에서 #### 구분선을 기준으로 위 코드는 Pypy3 제출에서 시간초과(대략 20% 정도에서), 아래 코드는 Pypy3 제출에서 "맞았습니다"가 나옵니다. 원리를 파악해봤을 때 위 코드는 방문기록용 리스트가 [[[0] * (k+1) for _ in range(m)] for _ in range(n)] 형태이고, 아래는 [[[0] * M for _ in range(N)] for k in range(K + 1)] 형태로 다르다는 점이 있습니다. 또한 queue 자료구조로 bfs 할 때 위 코드는 가장 안쪽의 튜플을 세 개의 인자로 구성했고 아래 코드는 네 개의 인자로 구성되었다는 점입니다. 이 다른 점이 어떤 영향으로 인해 실행 시간이 달라지게 되는 것인가요? 또는 이외의 다른 발견되는 차이점이 있다면 알려 주세요.

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

n, m, k = map(int, input().split())

graph = [list(map(int, input().rstrip())) for _ in range(n)]

visited = [[[0] * (k+1) for _ in range(m)] for _ in range(n)]

queue = deque([(0, 0, 0)])

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

answer = 1e9

visited[0][0][0] = 1

def bfs():
    global answer
    
    while queue:
        a, b, crash = queue.popleft()
        
        if a == n-1 and b == m-1:
            answer = visited[a][b][crash]
            return answer
        
        for i in range(4):
            r = a + dx[i]
            c = b + dy[i]
            if 0 <= r < n and 0 <= c < m:
                if graph[r][c] == 0 and visited[r][c][crash] == 0:
                    visited[r][c][crash] = visited[a][b][crash] + 1
                    queue.append((r, c, crash))
                elif graph[r][c] == 1 and visited[r][c][crash] == 0 and crash < k:
                    visited[r][c][crash+1] = visited[a][b][crash] + 1
                    queue.append((r, c, crash+1))
    return False

final = bfs()
if final:
    print(final)
else:
    print(-1)

#############################################################
#############################################################

import collections

def bfs(x, y):
    q = collections.deque()
    q.append([x, y, 0, 1])
    visited[0][x][y] = 1
    while q:
        x, y, crash, final = q.popleft()
        if x == N - 1 and y == M - 1:
            return final
        for dx, dy in direction:
            nxt_r, nxt_c = x + dx, y + dy
            if 0 <= nxt_r <= N - 1 and 0 <= nxt_c <= M - 1:
                if A[nxt_r][nxt_c] == 1 and crash < K and not visited[crash + 1][nxt_r][nxt_c]:
                    q.append([nxt_r, nxt_c, crash + 1, final + 1])
                    visited[crash + 1][nxt_r][nxt_c] = 1
                elif A[nxt_r][nxt_c] == 0 and not visited[crash][nxt_r][nxt_c]:
                    q.append([nxt_r, nxt_c, crash, final + 1])
                    visited[crash][nxt_r][nxt_c] = 1
    return -1


N, M, K = map(int, input().split())
A = [list(map(int, input())) for _ in range(N)]
visited = [[[0] * M for _ in range(N)] for k in range(K + 1)]
direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]
print(bfs(0, 0))

ilikerunning 2달 전 0

첫번째 코드에서는

elif graph[r][c] == 1 and visited[r][c][crash] == 0 and crash < k:

두번째 코드에서는

if A[nxt_r][nxt_c] == 1 and crash < K and not visited[crash + 1][nxt_r][nxt_c]:

로 차이가 있네요.

두번째 코드처럼 crash+1 된

visited[crash + 1][nxt_r][nxt_c] 를 확인하고 넘어가야 합니다.

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

문제

문제

출처

ICPC

두 코드의 걸린시간 차이가 발생하는 이유를 잘 모르겠습니다

sibaek 1년 전 0

ilikerunning 2달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말