복제 로봇

• 문제를 이해하는게 좀 어렵긴 한데, 결국 요구하는 것은 출발 위치와 모든 열쇠의 위치가 연결되도록 경로들을 만들고 경로의 합이 최소가 되게 하라는 것이고, 이것은 결국 각 위치들을 노드로 하는 그래프에서 최소 신장 트리 (Minimum Spanning Tree / MST)를 만들라는 뜻이다.
• 각 위치들을 노드로 하는 그래프를 만들고 나면 최소신장트리를 만드는 것은 어렵지 않다. 그렇지만, 그래프를 만들려면 각 노드들간의 거리를 모두 계산해줘야 한다. 미로의 칸의 수가 O(N^2)이므로, 그냥 플로이드 알고리즘으로 돌리면 O(N^6)..은 좀 힘들겠지만, 그냥 O(M)개의 출발지에서 모두 BFS를 돌리면 O(N^2M)에 필요한 거리들을 모두 계산할 수 있다. 이렇게 해서 만들어진 그래프는 O(M)개의 정점과 O(M^2)개의 엣지를 갖게 되고, 여기에서 MST를 찾는것은 크루스칼로 O(M^2logM) 또는 프림으로 O(M^2)에 가능하다.
• 실제 구현은 이것을 조금 더 효율적으로 하기 위해서, BFS과정과 MST과정을 합쳐보았다. 프림 알고리즘을 기반으로, 현재 추가된 점들로부터 가장 가까운 점을 찾고, 그 점을 MST에 추가하고 다시 가장 가까운 점을 찾는 것을 반복한다. 그러나, 가장 가까운 점을 찾는 것을 미리 계산해놓은 엣지 거리들을 이용하는 게 아니라, 그 시점에서 BFS를 돌려가면서 가장 가까운 점을 찾는다. 점이 추가되면서, 다른 점들과의 거리가 계속 다시 갱신되므로 힙을 사용해야 하고, BFS보다 dijkstra에 가깝게 동작한다. 이렇게 되면 시간복잡도는 O(M*N^2logN)으로 좀더 느려지는거 같지만, 실제로는 더 빠르게 돈다.

"""Solution code for "BOJ 1944. 복제 로봇".

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

import heapq

DELTAS = ((-1, 0), (1, 0), (0, -1), (0, 1))
START = 'S'
KEY = 'K'
WALL = '1'
INF = float('inf')


def main():
    N, M = [int(x) for x in input().split()]
    grid = [input() for _ in range(N)]

    for r, row in enumerate(grid):
        if (c := row.find(START)) >= 0:
            start_row, start_col = r, c
            break

    tot_dist = 0
    found_keys = 0
    dists = [[INF] * N for _ in range(N)]
    dists[start_row][start_col] = 0
    heap = [(0, start_row, start_col)]
    while heap:
        dist, r, c = heapq.heappop(heap)
        if dist > dists[r][c]:
            continue
        if grid[r][c] == KEY:
            tot_dist += dist
            found_keys += 1
            dists[r][c] = 0
            new_dist = 1
        else:
            new_dist = dist + 1
        for dr, dc in DELTAS:
            nr, nc = r + dr, c + dc
            if (0 <= nr < N and 0 <= nc < N and grid[nr][nc] != WALL and
                    new_dist < dists[nr][nc]):
                dists[nr][nc] = new_dist
                heapq.heappush(heap, (new_dist, nr, nc))

    print(tot_dist if found_keys == M else '-1')


if __name__ == '__main__':
    main()