테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 토마토 ======

===== 풀이 =====
  * 기본적인 BFS문제. 시작점이 여러곳이라는 것은 그냥 처음에 queue에 모든 시작점을 다 넣어놓고 탐색을 시작하면 된다.
  * [[ps:problems:boj:7569]]는 토마토 상자가 3차원으로 확장된 문제, [[ps:problems:boj:17114]]는 11차원으로 확장된 문제이다.
  * BFS만 돌리면 되므로, 시간 복잡도는 O(V+E)가 된다. 이 경우는 인접한 4방향의 셀로 엣지가 있는 셈이니까 E=O(4*V)=O(V)이고.. 그래서 시간 복잡도는 O(V+E)=O(V)=O(M*N)이 된다.
  * n차원 공간을 핸들링할때에, 1차원 배열에 저장하고 1차원 배열의 인덱스를 갖고서 처리하는게 더 효율적이고, 생각보다 코드도 그렇게 지저분해지지 않는다는 것을 [[ps:problems:boj:17114]]에서 깨달았다. 그래서 이 문제를 비롯해서 유사한 문제들을 전부 그런식으로 풀기로 했다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 7576. 토마토".

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

Tags: [BFS]
"""

from teflib import search

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


def main():
    def adj_tomatoes(cur_pos):
        y, x = divmod(cur_pos, M)
        delta = 1
        for coord_i, size_i in ((x, M), (y, N)):
            if coord_i > 0:
                next_pos = cur_pos - delta
                if tomatoes[next_pos] == UNRIPE:
                    yield next_pos
            if coord_i < size_i - 1:
                next_pos = cur_pos + delta
                if tomatoes[next_pos] == UNRIPE:
                    yield next_pos
            delta *= size_i

    M, N = [int(x) for x in input().split()]
    tomatoes = []
    for _ in range(N):
        tomatoes.extend(input().split())

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

    print(-1 if len(dists) < tomato_count else max(dists.values()))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:search#min_distances|teflib.search.min_distances]]

{{tag>BOJ ps:problems:boj:실버_1}}