글 읽기 - 코드를 개선하다 보니 시간초과가 뜹니다..

redpigeon 4년 전 0

기존에 풀었던 문제인데, 코드를 좀 개선해보고자 시도했지만... 시간초과가 납니다.

두 구문의 로직은 거의 동일한데, 왜 시간초과가 나는지 당최 알 수가 없습니다.

가장 깊은 if문 (next_loc[0], next_loc[1]의 조건을 확인하는 부분)에 print를 넣어서 얼마나 호출되는지 카운트 해봐도,

예제로 주어진 케이스들에서는 동일한 카운트 만큼 호출된 것으로 나옵니다. (복잡도 동일로 추정)

둘다 컨셉은 BFS이고, 다음에 탐색할 부분을 리스트로 queue에 넣어서 다음 번에 탐색하는.. 과정의 반복인데..

아무리 봐도 대체 왜 개선된 코드가 시간 초과가 뜨는지 모르겠습니다ㅠㅠㅠ

코드를 다 보셔야 해서.. 질문 자체가 좀 쉽지는 않겠습니다만..

너무 답답해서 며칠째 들여다보고 있다가 질문 올립니다ㅠㅠㅠㅠㅠ

답변 부탁드립니다ㅠㅠㅠ감사합니다(__)

import sys

M, N = map(int, sys.stdin.readline().split())

box = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
tomatoes = [(i, j) for i in range(N) for j in range(M) if box[i][j] == 1]


##### 개선된 코드, 시간초과 #####
count = 0
while len(tomatoes) != 0:
    for _ in range(len(tomatoes)):
        current_loc = tomatoes.pop(0)
        for i in range(4):
            next_loc = (current_loc[0] + [-1, 1, 0, 0][i], current_loc[1] + [0, 0, -1, 1][i])
            if 0 <= next_loc[0] < N and 0 <= next_loc[1] < M and box[next_loc[0]][next_loc[1]] == 0:
                box[next_loc[0]][next_loc[1]] = 1
                tomatoes.append(next_loc)

    count += 1

for line in box:
    if 0 in line:
        print(-1)
        exit()

print(count-1)
##### 개선된 코드, 시간초과 #####

##### 기존 코드, 정답 #####
# queue = [tomatoes]
# count = 0
# while True:
#     c = queue.pop(0)

#     next_cells = []
#     for cell in c:
#         for k in range(4):
#             next_loc = (cell[0] + [-1, 1, 0, 0][k], cell[1] + [0, 0, -1, 1][k])
#             if 0 <= next_loc[0] < N and 0 <= next_loc[1] < M and box[next_loc[0]][next_loc[1]] == 0:
#                 box[next_loc[0]][next_loc[1]] = 1                
#                 next_cells.append([next_loc[0], next_loc[1]])

#     queue.append(next_cells)
#     if len(next_cells) != 0:
#         count += 1
#     else:
#         break


# for line in box:
#     if 0 in line:
#         print(-1)
#         exit()

# print(count)
##### 기존 코드, 정답 #####

shg9411 4년 전 1

아래 코드와 비교를 해보지는 않아서 그 부분에 대해서는 드릴 말씀이 없지만

파이썬에서 list를 queue처럼 쓰실 경우 pop(0)에서 많은 시간이 소요됩니다.

deque를 사용하시는게 훨씬 효율적입니다. 만

deque로 고쳐서 내봤는데 시간초과가 나오진 않지만 아래 코드가 더 빠르게 나오네요.

redpigeon 4년 전 0

아..?!

정말 그렇네요

찾아보니 pop을 할때 list는 O(N)이고 deque는 O(1)이네요..

제 코드를 분석해보니

기존의 시간초과 코드는 매번 pop, append를 통해서 BFS가 이뤄지지만

밑의 정답 코드는 list를 통째로 pop해서 for문을 도는 구조라

pop횟수가 시간 초과 코드보다는 적어서 아무래도 시간적으로 이득을 보는게 아닐까 싶더라구요..

shg9411님 덕분에 많이 배우고 갑니다!

감사합니다~

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

문제

문제

출처

ICPC

코드를 개선하다 보니 시간초과가 뜹니다..

redpigeon 4년 전 0

shg9411 4년 전 1

redpigeon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말