글 읽기 - 토마토문제 시간초과가 뜹니다...ㅜㅜ

kitri04 5년 전 0

토마토 문제를 코딩했는데

테스트 케이스는 모두 정답을 내놓습니다.

그런데 채점 시 시간초과라고 뜨면서 오류가 나버리네요

3차원 리스트를 스캔 하는데 엄청난 시간을 잡아 먹는건가요?

계속 고민하다가 안 풀려서 질문 올려요

# 열, 행, 높
m, n, h = map(int,input().split())
tomato = [[[int(x) for x in input().split()] for _ in range(n)] for _ in range(h)]

def bfs():
    dx = [-1, 1, 0, 0, 0, 0]
    dy = [0, 0, -1, 1, 0, 0]
    dz = [0, 0, 0, 0, -1, 1]
    day = 0
    q = []
    isGrown = True

    # 잘 익은 토마토 위치를 큐에 넣기
    for k in range(h):
        for i in range(n):
            for j in range(m):
                if tomato[k][i][j] == 1:
                    q.append((k,i,j))
                elif tomato[k][i][j] == 0:
                    isGrown = False

    # 모든 토마토가 이미 익어 있을 때
    if isGrown:
        return 0

    # bfs로 탐색하면서 확장하기
    while q:
        step = len(q)
        for i in range(step):
            z, x, y = q.pop(0)

            for i in range(6):
                nx = x + dy[i]
                ny = y + dx[i]
                nz = z + dz[i]

                if (nx >= 0 and nx < n) and (ny >= 0 and ny < m) and (nz >=0 and nz < h):
                    if tomato[nz][nx][ny] == 0:
                        tomato[nz][nx][ny] = 1
                        q.append((nz, nx, ny))

        day += 1

    # 모두 익지 못할 때
    for k in range(h):
        for i in range(n):
            for j in range(m):
                if tomato[k][i][j] == 0:
                    return -1


    # 모두 익기까지 걸린 날짜
    return day


if __name__ == '__main__':
    print(bfs())

jh05013 5년 전 1

https://www.acmicpc.net/blog/v...

kitri04 5년 전 0

아!

파이썬에서는 리스트를 큐로 사용하면 시간복잡도가 어마어마해지네요.

감사합니다. 예전에 한 번 읽었던 글인데 잊고있었네요

큐 자료구조를 이용해 다시 해보겠습니다.

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

문제

문제

출처

ICPC

토마토문제 시간초과가 뜹니다...ㅜㅜ

kitri04 5년 전 0

jh05013 5년 전 1

kitri04 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말