문제 링크

• https://www.acmicpc.net/problem/17472

문제 설명

• 모든 섬을 다리로 연결
• 다리는 가로, 세로로 직선만 가능
• 다리 길이 2 이상
• 다리 길이 합의 최솟값 출력
• 연결이 불가능하면 -1 출력

풀이

• 섬에 번호를 매김
  • BFS
• 다리 리스트를 구함
  • 바다와 인접한 부분에서 다른 섬을 만날 때까지 직선 이동
• 다리 리스트에서 n-1개 선택
  • 크루스칼, Union-find

코드

import sys
from collections import deque


def init():
    ipt = sys.stdin.readline
    h, w = map(int, ipt().split())
    board = [list(map(int, ipt().split())) for _ in range(h)]
    dy, dx = [1,-1,0,0], [0,0,1,-1]
    return h, w, board, dy, dx, []


def set_board():
    num = 1
    visited = [[False] * w for _ in range(h)]
    for y in range(h):
        for x in range(w):
            if not visited[y][x] and board[y][x]:
                bfs(visited, (y, x), num)
                num += 1
    return num - 1


def bfs(visited, start, num):
    sy, sx = start
    visited[sy][sx] = True
    q = deque([start])
    while q:
        cy, cx = q.popleft()
        board[cy][cx] = num
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if 0 <= ny < h and 0 <= nx < w:
                if not visited[ny][nx] and board[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx))


def set_edge_list():
    for y in range(h):
        for x in range(w):
            if board[y][x]:
                for d in range(4):
                    bridge = get_bridge((y, x), d)
                    if bridge:
                        edge_list.append(bridge)
                    

def get_bridge(start, d):
    y, x = start
    n = board[y][x]
    length = 0
    while True:
        y = y + dy[d]
        x = x + dx[d]
        length += 1
        if 0 <= y < h and 0 <= x < w:
            if board[y][x]:
                if board[y][x] != n:
                    if length-1 >= 2:
                        return (n, board[y][x], length-1)
                    else:
                        return
                else:
                    return
            else:
            	continue
        else:
            return


def get_min_length():
    count = 0
    sum_cost = 0
    edge_list.sort(key=lambda x: x[2])
    parent = list(range(n+1))
    for a, b, cost in edge_list:
        ra = find_set(parent, a)
        rb = find_set(parent, b)
        if ra != rb:
            union(parent, ra, rb)
            sum_cost += cost
            count += 1
    if count == n-1:
        return sum_cost
    else:
        return -1


def find_set(parent, x):
    if parent[x] != x:
        parent[x] = find_set(parent, parent[x])
    return parent[x]


def union(parent, ra, rb):
    parent[ra] = rb


h, w, board, dy, dx, edge_list = init()
n = set_board()
set_edge_list()
print(get_min_length())