하이퍼 토마토

• 초끈이론의 영향을 받은 듯한 문제 설정이 충격적이지만, 결국은 토마토과 토마토의 단순한 확장. 똑같이 BFS로 풀면 된다. 시간 복잡도도 O(n)으로 동일하다 (n=셀의 갯수)
• 물론 BFS 알고리즘은 똑같더라도, 2차원이나 3차원 공간에서 적용했던 것처럼 11차원 리스트를 11중 포문으로 서치할수는 없으니.. (코드가 지저분한 것을 넘어서 파이썬에서는 속도도 문제가 된다).. 효율적으로 좌표를 처리하는 방법이 필요하다.
• 전체 공간을 그냥 1차원 리스트에 저장하고, 11차원 좌표를 1차원 리스트의 인덱스로 변환해서 탐색하는 식으로 처리했다. BFS 큐에는 인덱스를 저장하게 되는데, 특정셀의 정보는 인덱스만으로 빠르게 구할수 있지만, 인접한 셀을 찾을때는 좌표로 변환이 필요하다. 적어도 현재 셀이 바운더리에 걸려있는지를 체크하기 위해서는 각 차원의 좌표값을 알아야한다. 그래서 셀을 한번 처리할때마다, 인덱스를 좌표로 변환하고, 좌표에서 인접 셀의 좌표를 찾고 좌표를 다시 인덱스로 변환하는 방식으로 코드를 만들었으나, python으로 제출하자 TLE에 걸렸다.
• 처음에는 다른 쪽에서 시간을 줄이기 위해서 teflib.search.min_distances 를 그대로 사용하지 않고, 이 문제에 맞게 최적화 시키는 방식을 시도했다. 사실 이 문제에서는 모든 셀에 대한 distance를 다 구해서 갖고 있을 필요가 없으니, 최적화할 여지는 많이 있었지만, 그걸로는 TLE를 해결하지 못했다.
• 그 대신 좌표 탐색쪽을 더 코드를 정리하는 방식으로 통과시키는데에 성공했다. 인덱스를 좌표로 변환해서 바운더리 체크를 하는 것은 동일하지만 인접 좌표의 인덱스를, 좌표→인덱스 변환을 통해서 계산하지 않고, 바로 현재 인덱스에서 계산하는 방식으로 처리했더니 통과될수 있었다. 코드도 나름 좀더 깔끔해졌다. 통과되는 코드를 만들어놓고 나니, teflib.search.min_distances를 그대로 사용할지 수정해서 쓸지 여부는 400ms정도 밖에 영향을 주지 않았다.
• 완성된 코드는 차원 갯수를 따로 지정하지 않았기 때문에 토마토과 토마토에 그대로 제출해도 통과된다
• 그리고 이 문제의 함정은 토마토과 토마토 에는 존재하는 '토마토가 하나 이상 있는 경우만 입력으로 주어진다.' 조건이 여기에만 없다는 것.

"""Solution code for "BOJ 17114. 하이퍼 토마토".

- Problem link: https://www.acmicpc.net/problem/17114
- Solution link: http://www.teferi.net/ps/problems/boj/17114

Tags: [BFS]
"""

import functools
import operator
import sys
from teflib import search

EMPTY = '-1'
RIPE = '1'
UNRIPE = '0'


def main():
    def adj_tomatoes(pos):
        p = pos
        delta = 1
        for size_i in sizes:
            p, coord_i = divmod(p, size_i)
            if coord_i > 0:
                next_pos = pos - delta
                if tomatoes[next_pos] == UNRIPE:
                    yield next_pos
            if coord_i < size_i - 1:
                next_pos = pos + delta
                if tomatoes[next_pos] == UNRIPE:
                    yield next_pos
            delta *= size_i

    sizes = [int(x) for x in sys.stdin.readline().split()]
    line_count = functools.reduce(operator.mul, sizes[1:])
    tomatoes = []
    for _ in range(line_count):
        tomatoes.extend(sys.stdin.readline().split())

    ripe_tomatoes = [i for i, x in enumerate(tomatoes) if x == RIPE]
    tomato_count = sum(1 for x in tomatoes if x != EMPTY)
    dists = search.min_distances(adj_tomatoes, ripe_tomatoes)

    print(-1 if len(dists) < tomato_count else max(dists.values(), default=0))


if __name__ == '__main__':
    main()

• Dependency: teflib.search.min_distances