글 읽기 - 7569번 질문 드립니다. (Python3 / 시간 초과)

ohyuni 4년 전 0

안녕하세요.

7569번 문제를 푸는데 시간 초과 문제가 발생해서 질문 드립니다.

제 코드에서 불필요한 부분이나 개선할 수 있는 부분이 있다면 알려주시면 고맙겠습니다.

감사합니다.

import sys
import collections # deque 사용

# 주어진 값이 범위 내에 있는지 확인
def is_in_range(H, N, M, h, r, c):
    return h >= 0 and r >= 0 and c >= 0 and \
           h < H and r < N and c < M

# 입력 읽어오기 / visited 배열 생성 및 초기화
M, N, H = map(int, sys.stdin.readline().split())
box = [[] for _ in range(H)]
visited = [[[False]*M for _ in range(N)] for _ in range(H)]
for i in range(H):
    for _ in range(N):
        box[i].append(sys.stdin.readline().split())

# 익은 토마토를 queue에 넣기!! / 토마토 개수 세기
for i in range(H):
    for j in range(N):
        for k in range(M):
            if box[i][j][k] == '1':
                queue.append((i, j, k, 0))
            if box[i][j][k] == '-1':
                number_of_tomato -= 1

days_to_ripen = 0 # 토마토가 모두 익을 때까지 며칠이 걸리는지

# BFS 수행 / queue에서 토마토를 꺼낼 때마다 토마토 개수 1씩 감소
while queue:
    h, r, c, days_to_ripen = queue.popleft()
    number_of_tomato -= 1
    direction = [(-1, 0, 0), (1, 0, 0), (0, -1, 0),
                 (0, 1, 0), (0, 0, -1), (0, 0, 1)]
    for i, j, k in direction:
        if is_in_range(H, N, M, h+i, r+j, c+k) and \
           not visited[h+i][r+j][c+k] and \
           box[h+i][r+j][c+k] == '0':
            queue.append((h+i, r+j, c+k, days_to_ripen+1))
            visited[h+i][r+j][c+k] = True

print(days_to_ripen if number_of_tomato == 0 else -1)

ohyuni 4년 전 0

PyPy3로 제출하여 통과했습니다.

Python3로 제출하여 통과하는 방법은 없을까요?

어느 부분이 오래 걸리는지 알고 싶습니다.

indioindio 4년 전 0

이 코드를 제출하면 런타임에러가 납니다.

ohyuni 4년 전 0

주석 문제 같습니다.

시간 초과 받은 코드 그대로 복사하여 첨부합니다.

import sys
import collections


def is_in_range(H, N, M, h, r, c):
    return h >= 0 and r >= 0 and c >= 0 and \
           h < H and r < N and c < M

M, N, H = map(int, sys.stdin.readline().split())
box = [[] for _ in range(H)]
visited = [[[False]*M for _ in range(N)] for _ in range(H)]
for i in range(H):
    for _ in range(N):
        box[i].append(sys.stdin.readline().split())

queue = collections.deque([])
number_of_tomato = M*N*H
for i in range(H):
    for j in range(N):
        for k in range(M):
            if box[i][j][k] == '1':
                queue.append((i, j, k, 0))
            if box[i][j][k] == '-1':
                number_of_tomato -= 1

days_to_ripen = 0

while queue:
    h, r, c, days_to_ripen = queue.popleft()
    number_of_tomato -= 1
    direction = [(-1, 0, 0), (1, 0, 0), (0, -1, 0),
                 (0, 1, 0), (0, 0, -1), (0, 0, 1)]
    for i, j, k in direction:
        if is_in_range(H, N, M, h+i, r+j, c+k) and \
           not visited[h+i][r+j][c+k] and \
           box[h+i][r+j][c+k] == '0':
            queue.append((h+i, r+j, c+k, days_to_ripen+1))
            visited[h+i][r+j][c+k] = True
            box[h+i][r+j][c+k] = '1'

print(days_to_ripen if number_of_tomato == 0 else -1)

ohyuni 4년 전 0

주석을 입력하면서 한글 입력 오류(??)가 발생하길래 그 부분을 지웠는데 그와 함께 코드 일부분이 지워져서 런타임 에러가 발생하네요 ㅠㅠ

신중하게 확인하지 못한 점 죄송합니다.

indioindio 4년 전 1

알고리즘 자체의 개선사항은 python3 정답자들의 코드를 확인하는 것이 좋을 것 같고,

저는 기술적인 부분만 조금 수정해보았습니다.

box = [[sys.stdin.readline().split() for i in range(N)] for j in range(H)] 로 append 대신 box의 생성 시점에서 입력을 받게끔 하였고

nh, nr, nc = h+i, r+j, c+k 로 중복된 덧셈 계산을 줄여보았습니다. 4452ms 로 통과하네요.

loop unrolling을 사용하면 더 성능이득을 볼 수 있습니다만, (https://www.acmicpc.net/source/13576932) 다른 개선방안을 참조하는 것이 더 좋을 것 같네요.

import sys
import collections # deque 사용

# 주어진 값이 범위 내에 있는지 확인
def is_in_range(H, N, M, h, r, c):
    return h >= 0 and r >= 0 and c >= 0 and \
           h < H and r < N and c < M

# 입력 읽어오기 / visited 배열 생성 및 초기화
M, N, H = map(int, sys.stdin.readline().split())
box = [[sys.stdin.readline().split() for i in range(N)] for j in range(H)]
not_visited = [[[1]*M for _ in range(N)] for _ in range(H)]
number_of_tomato = M*N*H
queue = collections.deque()
days_to_ripen = 0 # 토마토가 모두 익을 때까지 며칠이 걸리는지

direction = ((-1, 0, 0), (1, 0, 0), (0, -1, 0),
             (0, 1, 0), (0, 0, -1), (0, 0, 1))

for i in range(H):
    for j in range(N):
        for k in range(M):
            if box[i][j][k] == '1':
                queue.append((i, j, k, 0))
            elif box[i][j][k] == '-1':
                number_of_tomato -= 1


# BFS 수행 / queue에서 토마토를 꺼낼 때마다 토마토 개수 1씩 감소
while queue:
    h, r, c, days_to_ripen = queue.popleft()
    number_of_tomato -= 1
    for i, j, k in direction:
        nh, nr, nc = h+i, r+j, c+k
        if nh >= 0 and nr >= 0 and nc >= 0 and nh < H and nr < N and nc < M:
            if not_visited[nh][nr][nc] and box[nh][nr][nc] == '0':
                queue.append((nh, nr, nc, days_to_ripen+1))
                not_visited[nh][nr][nc] = False

print(days_to_ripen if number_of_tomato == 0 else -1)

indioindio 4년 전 0

is_in_range 함수호출 대신 if 문 내에서 전부 비교했다는 내용을 빼먹었습니다.

ohyuni 4년 전 1

확인했습니다.

답변 감사합니다.

알려주신 부분 모두 모르고 있던 내용이었는데 답변을 통해 배우고 가요.

말씀하신대로 다른 알고리즘 자체의 개선 방안 역시 찾아보겠습니다.

깨달음 주셔서 감사합니다.

좋은 하루 되세요 :D

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

문제

문제

출처

ICPC

7569번 질문 드립니다. (Python3 / 시간 초과)

ohyuni 4년 전 0

ohyuni 4년 전 0

indioindio 4년 전 0

ohyuni 4년 전 0

ohyuni 4년 전 0

indioindio 4년 전 1

indioindio 4년 전 0

ohyuni 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말