글 읽기 - [파이썬] 두 코드의 차이가 뭔가요?

ojm6135 2년 전 0

첫 번째 코드는 bfs를 수행한 뒤에 아직 익지 않은 토마토가 있는지 탐색하는 코드이고

두 번째는 bfs 전에 익지 않은 토마토를 카운트 한 값을 저장하고, bfs를 수행하면서 카운트를 -1씩 해주도록 했습니다.

실제로 첫 번째 코드가 두 번째 코드보다 더 시간이 빠르게 나왔습니다.

저는 for문을 도는 것보다 개수를 카운트 하는 방식이 더 빠를 거라고 생각했는데 왜 for문을 도는 것이 더 빠른지 궁금합니다.

import sys
from collections import deque

input = sys.stdin.readline


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

tomatoes = [ [] for _ in range(h) ]

queue = deque()

for dep in range(h):
    for r in range(n):
        tomatoes[dep].append( list(map(int, input().split())) )

        for c in range(m):
            if tomatoes[dep][r][c] == 1:
                queue.append( (dep, r, c) )


day = -1
d = [ (-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1) ]

while queue:
    day += 1

    for _ in range( len(queue) ):
        dep, r, c = queue.popleft()
        
        for ddep, dr, dc in d:
            new_dep = dep + ddep
            new_r = r + dr
            new_c = c + dc

            if 0 <= new_dep < h and 0 <= new_r < n and 0 <= new_c < m:
                if tomatoes[new_dep][new_r][new_c] == 0:
                    tomatoes[new_dep][new_r][new_c] = 1
                    queue.append( (new_dep, new_r, new_c) )


for dep in range(h):
    for r in range(n):
        for c in range(m):
            if tomatoes[dep][r][c] == 0:
                day = -1
                break


print(day)

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

import sys
from collections import deque

input = sys.stdin.readline


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

tomatoes = [ [] for _ in range(h) ]

queue = deque()

cnt = 0

for dep in range(h):
    for r in range(n):
        tomatoes[dep].append( list(map(int, input().split())) )

        for c in range(m):
            if tomatoes[dep][r][c] == 1:
                queue.append( (dep, r, c) )
            elif tomatoes[dep][r][c] == 0:
                cnt += 1


day = -1
d = [ (-1, 0, 0), (1, 0, 0), (0, -1, 0), (0, 1, 0), (0, 0, -1), (0, 0, 1) ]

while queue:
    day += 1

    for _ in range( len(queue) ):
        dep, r, c = queue.popleft()
        
        for ddep, dr, dc in d:
            new_dep = dep + ddep
            new_r = r + dr
            new_c = c + dc

            if 0 <= new_dep < h and 0 <= new_r < n and 0 <= new_c < m:
                if tomatoes[new_dep][new_r][new_c] == 0:
                    tomatoes[new_dep][new_r][new_c] = 1
                    queue.append( (new_dep, new_r, new_c) )
                    cnt -= 1


print(-1 if cnt else day)

Green55 2년 전 1

4.3초 / 4.4초 정도의 차이인데, 이 정도면 제출할때 마다 달라질 수도 있는 정도의 값입니다.

그냥 유의미한 차이가 없다고 생각하시면 될 것 같습니다.

ojm6135 2년 전 0

그렇군요.. 답변 감사합니다!!

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

문제

문제

출처

ICPC

[파이썬] 두 코드의 차이가 뭔가요?

ojm6135 2년 전 0

Green55 2년 전 1

ojm6135 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말