글 읽기 - 61% 마의 벽을 깰 수 있게 도와주세요.

2chanhaeng 1년 전 0

안녕하세요.

61%에서 시간 초과의 벽을 뚫지 못하고 좌절하고 있는 플밍뉴비 입니다.

원래 예쁘게 좀 작성해보겠다고 itertools.product 같은 클래스도 갖다 쓰고 했는데 통과를 못해서 가독성이고 뭐고 다 포기하고 이 꼬라지로 코드를 작성했는데도 속도가 나오질 않고 있습니다...

조언 부탁드립니다.

혹시 필요하시다면 제 이전 코드는 제 깃헙에 모아있습니다.

2천줄 짜리 예제도 있으니 아직 저처럼 못 푸신 분들 필요하시면 참고하세요.

def solution(input):
    m, n, o, p, q, r, s, t, u, v, w = list(map(int, input().split()))
    # m ~ w 까지 입력받습니다.
    tomatoes = {}
    # 격자간 토마토의 상태를 저장할 딕셔너리를 생성합니다.
    for W in range(w):
        for V in range(v):
            for U in range(u):
                for T in range(t):
                    for S in range(s):
                        for R in range(r):
                            for Q in range(q):
                                for P in range(p):
                                    for O in range(o):
                                        for N in range(n):
                                            for M, i in zip(range(m), map(int, input().split())):
                                                tomatoes[(M, N, O, P, Q, R, S, T, U, V, W)] = i
                                                # 마지막에만 입력받은 숫자를 상태로써 저장합니다.
    # 키는 토마토의 좌표, 값은 토마토의 상태입니다.
    mm, nm, om, pm, qm, rm, sm, tm, um, vm, wm = m-1, n-1, o-1, p-1, q-1, r-1, s-1, t-1, u-1, v-1, w-1
    # 매번 1을 빼는 것도 시간이 걸릴까봐 변수로 지정했습니다.
    def side(points, empty):
        # 주변 토마토를 찾는 함수입니다.
        sides = set()
        # 최종적으로 반환할 집합입니다.
        for point in points:
            M, N, O, P, Q, R, S, T, U, V, W = point
            # 0 보다 크면, +1 좌표를 추가합니다.
            # 최대보다 작으면, -1 좌표를 추가합니다.
            if M < mm: sides.add((M + 1, N, O, P, Q, R, S, T, U, V, W))
            if M > 0:  sides.add((M - 1, N, O, P, Q, R, S, T, U, V, W))
            if N < nm: sides.add((M, N + 1, O, P, Q, R, S, T, U, V, W))
            if N > 0:  sides.add((M, N - 1, O, P, Q, R, S, T, U, V, W))
            if O < om: sides.add((M, N, O + 1, P, Q, R, S, T, U, V, W))
            if O > 0:  sides.add((M, N, O - 1, P, Q, R, S, T, U, V, W))
            if P < pm: sides.add((M, N, O, P + 1, Q, R, S, T, U, V, W))
            if P > 0:  sides.add((M, N, O, P - 1, Q, R, S, T, U, V, W))
            if Q < qm: sides.add((M, N, O, P, Q + 1, R, S, T, U, V, W))
            if Q > 0:  sides.add((M, N, O, P, Q - 1, R, S, T, U, V, W))
            if R < rm: sides.add((M, N, O, P, Q, R + 1, S, T, U, V, W))
            if R > 0:  sides.add((M, N, O, P, Q, R - 1, S, T, U, V, W))
            if S < sm: sides.add((M, N, O, P, Q, R, S + 1, T, U, V, W))
            if S > 0:  sides.add((M, N, O, P, Q, R, S - 1, T, U, V, W))
            if T < tm: sides.add((M, N, O, P, Q, R, S, T + 1, U, V, W))
            if T > 0:  sides.add((M, N, O, P, Q, R, S, T - 1, U, V, W))
            if U < um: sides.add((M, N, O, P, Q, R, S, T, U + 1, V, W))
            if U > 0:  sides.add((M, N, O, P, Q, R, S, T, U - 1, V, W))
            if V < vm: sides.add((M, N, O, P, Q, R, S, T, U, V + 1, W))
            if V > 0:  sides.add((M, N, O, P, Q, R, S, T, U, V - 1, W))
            if W < wm: sides.add((M, N, O, P, Q, R, S, T, U, V, W + 1))
            if W > 0:  sides.add((M, N, O, P, Q, R, S, T, U, V, W - 1))
        return sides & empty
        # 그 중에서 익지 않은 토마토의 좌표만 가져옵니다.
    empty, changed = set(), set()
    # empty 는 익지 않은 토마토의 좌표가 저장될 집합입니다.
    # changed 는 비어있거나 바뀐 토마토의 좌표가 저장될 집합입니다.
    tochange = set()
    # tochange 는 상태가 바뀔 토마토의 좌표가 저장될 집합입니다.
    # 다만 0번째에 들어가기 전, 즉 -1번째 날(가정)에는 익은 토마토들의 자리를 저장합니다.
    # 그래야 0번째 날에 익은 토마토가 되기 때문입니다.
    for key, value in tomatoes.items():
        # 토마토의 좌표와 상태를 가져옵니다.
        if value == 1:
            # 익은 토마토라면,
            changed.add(key)
            # 좌표를 익은 토마토 좌표와
            tochange.add(key)
            # 바뀔 토마토 좌표에 추가합니다.
        elif value:
            # 비어있다면,
            changed.add(key)
            # 좌표를 빈 자리 좌표에 추가합니다.
        else:
            # 둘 다 아니라면,
            empty.add(key)
            # 좌표를 익지 않은 토마토 좌표에 추가합니다.
    for days in range(m*n*o*p*q*r*s*t*u*v*w):
        # 날을 세는 반복문입니다.
        # 최댓값을 격자의 칸 수로 두었습니다.
        tochange = side(tochange, empty)
        # 오늘 익을 토마토의 집합을 전날 바뀔 토마토의 집합으로 구합니다.
        empty -= tochange
        # 바뀔 토마토의 집합을 익지 않은 토마토 집합에서 제거합니다.
        changed |= tochange
        # 바뀐 토마토의 집합에 익은 토마토 좌표에 추가합니다.
        if not tochange: break
        # 바뀔 토마토의 집합이 비었다면 반복문을 종료합니다.
    print(-1 if empty else days)
    # 익지 않은 토마토가 남았다면 -1을 출력하고, 아니라면 며칠이 걸렸는지 출력합니다.
import sys
solution(lambda: sys.stdin.readline().rstrip())

2chanhaeng 1년 전 0

input 함수를 lambda: sys.stdin.readline().rstrip() 대신 iter(open(0).read().split("\n")).__next__ 으로 재정의하여 해결했습니다. 아무래도 보기가 여러줄로 이루어져 있다보니 알고리즘도 알고리즘이지만 입력을 어떻게 받는지가 꽤 중요한 것 같더라구요.

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

문제

문제

출처

ICPC

61% 마의 벽을 깰 수 있게 도와주세요.

2chanhaeng 1년 전 0

2chanhaeng 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말