글 읽기 - 파이썬 시간초과 질문..!

yjh8707 1년 전 0

라이브러리를 최대한 안쓰는 방향으로 코드를 늘 작성하여서 큐를 구현할 때 .pop(0) 을 사용 하였습니다.

시간초과 때문에 sys도 넣었지만 여전히 시간초과입니다.

.pop(0) 을 사용하는 list의 경우 O(N), deque를 import 하여 사용하면 O(1) 라고 알고 있습니다.

이 문제에 대해서는 무조건 deque 를 사용해야 시간초과를 통과할 수 있을까요 ?

다른 방법이 있다면 시간이 많이 걸릴만한 부분을 체크해주시면 감사하겠습니다.

import sys

M, N = map(int, sys.stdin.readline().rstrip().split())
graph = []
queue = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(N):
    g = list(map(int, sys.stdin.readline().rstrip().split()))
    graph.append(g)

for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            queue.append((i, j))
        graph[i][j] -= 1  # day0 부터 진행하기 위함

while queue:
    x, y = queue.pop(0)
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx <= -1 or nx >= N or ny <= -1 or ny >= M:
            continue
        if graph[nx][ny] == -1:  # 안 익은 토마토에 대해서만
            queue.append((nx, ny))
            graph[nx][ny] = graph[x][y] + 1

ans = 0
for m in range(N):
    if graph[m].count(-1) != 0:  # 안 익은 토마토가 있다면 ( 0 - 1 = -1, line 17 )
        ans = -1
        break
    else:
        ans = max(max(graph[m]), ans)  # 가장 늦게 익은 토마토의 day

print(ans)

marshal1101 1년 전 1

stack으로 바꾸고, 기존 토마토와 다음 토마토 정보를 분리하시면 되네요.

while stack:
    new_stack = []
    while stack:
        x, y = stack.pop()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx <= -1 or nx >= N or ny <= -1 or ny >= M:
                continue
            if graph[nx][ny] == -1:  # 안 익은 토마토에 대해서만
                new_stack.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
    stack = new_stack

yjh8707 1년 전 0

현재 익은 토마토에 대해서만 진행하면 되니 순서가 상관이 없어 stack 을 사용해도 되는거였군요 ! 감사합니다 !

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

문제

문제

출처

ICPC

파이썬 시간초과 질문..!

yjh8707 1년 전 0

marshal1101 1년 전 1

yjh8707 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말