다리 만들기 2

• 최소 신장 트리 (Minimum Spanning Tree / MST)를 구하기만 하면 되는 문제이다.
• 다만 구현이 조금 번거롭다. 주어진 지도를 그래프로 변환하는 작업이 귀찮다.
• 각각의 섬이 하나의 노드에 대응되는 그래프를 만들기 위해서는, 먼저 그리드에서 커넥티드 컴포넌트들을 추출해서 섬을 만들고, 설치 가능한 다리들이 어떤 섬과 어떤 섬을 연결하는지를 찾아서 엣지들을 만들어주는 귀찮은 작업이 필요하다.
  • DFS를 돌려서 커넥티드 컴포넌트들을 추출하고, 설치 가능한 다리들을 찾고 하는것들은 모두 O(N*M)에 처리 가능하다. 이렇게 해서 그래프를 만들면, 섬의 갯수가 V개 (문제에서의 제한은 6개)이하라는 제한이 있으므로, MST를 찾는 것은 O(V*2logV) 또는 프림 알고리즘을 쓰면 O(V*2)에도 가능하다.
• 살짝 느리더라도 코딩을 간단히 하는 방법은, 그냥 땅에 해당되는 각각의 셀을 전부 노드로 하는 그래프를 만드는 것이다. 다리로 연결 가능한 땅들간에 간선을 만들어 주는 것에 추가적으로 인접한 땅 사이를 가중치가 0인 간선으로 연결해준다. 이렇게 그래프를 만들어놓고 그냥 MST 알고리즘을 돌려도 결과는 동일하게 나온다.
  • 다리를 모두 찾는 번거로운 작업은 여기서도 필요하지만 커넥티드 컴포넌트를 찾는 과정은 생략할수 있어졌다. 시간 복잡도는 그래프를 만드는 데에 O(N*M)이고, 이렇게 만들어진 그래프의 노드 수와 엣지 수는 모두 O(N*M)이므로, MST를 찾는데에는 O(N*M*log(N*M))이 걸린다. 총 시간복잡도는 O(N*M*log(N*M))으로 앞의 방법에서의 O(N*M + V^2)보다 느리긴 하지만, 구현의 편의성때문에 이 방법으로 코딩했다.

"""Solution code for "BOJ 17472. 다리 만들기 2".

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

Tags: [Implementation] [MST]
"""

import itertools
from teflib import tgraph

SEA = -1


def main():
    N, M = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    grid = []
    id_iter = itertools.count()
    for _ in range(N):
        row = input().split()
        grid.append([next(id_iter) if x == '1' else SEA for x in row])

    edges = []
    rows, cols = grid, list(zip(*grid))
    for line in rows + cols:
        u, length = None, 0
        for prev, cur in zip(line, line[1:]):
            if prev == cur == SEA:
                length += 1
            elif prev == SEA:
                if length > 1 and u is not None:
                    edges.append((length, u, cur))
            elif cur == SEA:
                u, length = prev, 1
            else:
                edges.append((0, prev, cur))

    try:
        land_count = next(id_iter)
        answer = tgraph.minimum_spanning_tree_from_edges(land_count, edges)
    except ValueError:
        answer = -1
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.minimum_spanning_tree_from_edges