[Gold I] 다리 만들기 2 - 17472

문제 링크

성능 요약

메모리: 35140 KB, 시간: 64 ms

분류

구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리

문제 설명

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

---

문제 풀이

문제 분석

이 문제는 N x M 크기의 격자 지도에서 섬들을 연결하는 다리를 건설하는 최소 비용을 찾는 문제입니다. 섬은 연결된 땅(1)으로 이루어진 덩어리이고, 다리는 바다(0)에 건설해야 하며, 길이는 2 이상이어야 합니다. 다리는 가로 또는 세로 방향으로만 건설 가능하며, 중간에 방향이 바뀌면 안됩니다. 모든 섬을 연결할 수 있다면 최소 다리 길이의 합을 출력하고, 불가능하면 -1을 출력해야 합니다.

접근 방법

이 문제는 그래프 이론과 최소 스패닝 트리(MST) 알고리즘을 사용하여 해결할 수 있습니다.

1. 섬 라벨링: BFS(너비 우선 탐색)를 사용하여 지도에서 각 섬을 구분하고 고유한 번호를 할당합니다.
2. 다리 건설: 각 섬에서 다른 섬으로 다리를 건설할 수 있는 모든 경우를 탐색하고, 다리 길이와 연결된 섬 정보를 저장합니다.
3. MST 구성: Kruskal 또는 Prim 알고리즘을 사용하여 최소 스패닝 트리를 구성합니다. MST 알고리즘은 모든 섬을 연결하는 최소 비용의 다리 조합을 찾습니다.
4. 결과 확인: MST를 구성한 후 모든 섬이 연결되었는지 확인하고, 연결되지 않았다면 -1을 출력합니다. 연결되었다면 MST에 포함된 다리 길이의 합을 출력합니다.

구현 설명

1. 섬 라벨링 (BFS)

• 지도 전체를 순회하면서 땅(1)을 발견하면 BFS를 시작합니다.
• BFS를 통해 연결된 모든 땅을 같은 섬 번호(idx)로 라벨링합니다.
• visited 배열을 사용하여 이미 방문한 땅을 추적하여 중복 방문을 방지합니다.
• islands 큐에 섬의 좌표, 섬 번호, 다리 길이(초기값 0), 방향 정보를 함께 저장합니다. 방향 정보는 각 섬 위치에서 상, 하, 좌, 우 4방향으로 다리를 놓을 수 있는 가능성을 나타냅니다.

2. 다리 건설 및 정보 저장

• islands 큐에서 섬 좌표 정보를 하나씩 꺼내어 상, 하, 좌, 우 4방향으로 다리를 건설할 수 있는지 탐색합니다.
• 다리를 건설하는 동안 바다(0)를 만나면 다리 길이를 늘려가며 탐색을 계속합니다.
• 다른 섬을 만나고 다리 길이가 2 이상이면, 두 섬과 다리 길이를 dist 리스트에 저장합니다.
• 다리를 건설할 수 없는 경우(지도를 벗어나는 경우)는 탐색을 중단합니다.

3. 최소 스패닝 트리 (Kruskal)

• dist 리스트를 다리 길이(w)를 기준으로 정렬합니다.
• Kruskal 알고리즘을 사용하여 MST를 구성합니다. Union-Find 자료 구조를 사용하여 사이클 생성을 방지합니다.
• find(x) 함수는 섬 x가 속한 집합의 대표 노드를 찾습니다.
• union(a, b) 함수는 섬 a와 섬 b가 속한 집합을 합칩니다.
• MST에 포함된 다리 길이의 합을 answer 변수에 누적합니다.

4. 결과 확인

• Union-Find를 통해 모든 섬이 하나의 집합으로 연결되었는지 확인합니다. roots 변수를 사용하여 모든 섬의 대표 노드 set을 구하고, set의 크기가 1인지 확인합니다.
• 모든 섬이 연결되지 않았다면 -1을 출력하고, 연결되었다면 answer를 출력합니다.

⏱복잡도 분석

• 시간 복잡도:

  • BFS: O(N*M) - 모든 칸을 방문할 수 있으므로
  • 다리 건설: O(N*M*4*max(N,M)) - 모든 섬에서 최악의 경우 지도의 끝까지 탐색
  • Kruskal: O(E log E) (E는 간선의 수)
  • 전체: O(N*M*log(N*M))

• 공간 복잡도:

  • graph, visited: O(N*M)
  • islands: O(N*M)
  • dist: O((N*M)^2) - 최악의 경우 모든 섬 쌍 사이에 다리가 존재할 수 있음
  • Union-Find parents: O(섬의 개수) <= O(N*M)
  • 전체: O(N*M + (N*M)^2)

핵심 포인트

1. 섬 라벨링: BFS를 사용하여 효율적으로 섬을 구분하고 라벨링하는 것이 중요합니다.
2. 다리 건설 조건: 다리 길이는 2 이상이어야 하고, 방향이 바뀌면 안 되며, 섬과 인접한 바다 위에 건설되어야 합니다.
3. MST 알고리즘 선택: Kruskal 또는 Prim 알고리즘을 사용하여 최소 비용으로 모든 섬을 연결해야 합니다. Union-Find 자료구조를 이용하여 사이클을 효과적으로 관리해야 합니다.

풀이 코드

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())

graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

islands = deque()
visited = [[False] * m for i in range(n)]


directions = [(1,0),(-1,0),(0,1),(0,-1)]
def BFS(graph, visited, i,j,idx,islands):
    queue = deque()
    queue.append((i,j))
    visited[i][j] = True
    islands.append((i,j,idx,0,0))
    islands.append((i,j,idx,0,1))
    islands.append((i,j,idx,0,2))
    islands.append((i,j,idx,0,3))
    graph[i][j] = idx
    while queue:
        x,y = queue.popleft()
        for dx,dy in directions:
            sx,sy = x+dx, y+dy
            if 0<=sx<n and 0<=sy<m and not visited[sx][sy] and graph[sx][sy]==1:
                visited[sx][sy]=True
                queue.append((sx,sy))
                graph[sx][sy] = idx
                islands.append((sx,sy,idx, 0,0))
                islands.append((sx,sy,idx, 0,1))
                islands.append((sx,sy,idx, 0,2))
                islands.append((sx,sy,idx, 0,3))


idx = 1
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visited[i][j]:
            BFS(graph,visited,i,j,idx,islands)
            idx+=1

dist = []
while True:
    new_islands = deque()
    while islands:
        x,y,island,cnt,pos = islands.popleft()            
        dx,dy = directions[pos]
        sx,sy = x+dx,y+dy
        if 0<=sx<n and 0<=sy<m:
            if graph[sx][sy] == 0:
                new_islands.append((sx,sy,island,cnt+1,pos))
            
            elif not graph[sx][sy] == 0 and not island == graph[sx][sy] and cnt > 1:
                dist.append([island, graph[sx][sy], cnt])
        
    islands = new_islands

    if not islands:
        break

parents = {}
answer = 0
def find(x):
    if x not in parents:
        parents[x] = x

    if parents[x] != x:
        parents[x] = find(parents[x])

    return parents[x]

def union(a,b):
    a = find(a)
    b = find(b)
    if find(a) != find(b):
        parents[a] = b

dist.sort(key= lambda x:x[2])
for x,y,w in dist:
    if find(x) != find(y):
        union(x,y)
        answer += w

roots = set(find(i) for i in range(1, idx))

if len(roots) == 1:
    print(answer)
else:
    print(-1)