[BOJ/백준] 17472 다리 만들기 2 파이썬

문제 링크 : https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

예전에 풀었던 걸 MST로 다시 풀어봤다.

예전에는 BFS,DFS로 완탐으로 해결했었다.

 

이번에는 BFS, MST로 해결했다.

 

BFS로 각 섬에 번호 매기면서 섬의 가장자리를 구한다.

이때 해당 점에서 이동하려는 점이 격자판 안에 있고 물인 경우 가장자리로 판별해서 저장했다.

(x,y,방향) 이때 방향은 해당 칸으로 온 방향이다.

 

구한 가장자리에서 다리를 만들면서 유효한 다리 정보를 생성한다.

이때는 구한 가장자리의 정보를 가지고 다리를 생성한다.

저장한 방향정보 가지고 범위를 벗어나거나 다른 섬을 만날때까지 진행한다.

다른 섬을 만났다면 다리 정보를 생성하자.

(출발 다리 번호, 도착 다리 번호, 길이)

 

다음 다리 정보를 길이순으로 오름차순해서 정렬한 후 MST에  사용하자

 

마지막 MST는 크루스칼을 이용했다.

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

n,m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
edges = []

def solv():
    global parent
    max_num = set_area_num()

    parent = [i for i in range(max_num)]
    candidate_bridge = set_candidate_bridge()

    print(kruskal(candidate_bridge,max_num))
def kruskal(candidate_bridge, max_num):
    bridge_count = 0
    length = 0

    for a,b,c in candidate_bridge:
        if not is_same_parent(a,b):
            union(a,b)
            bridge_count += 1
            length += c
            if bridge_count == max_num-3:
                return length
    return -1

def find(target):
    global parent
    if parent[target] == target:
        return target
    parent[target] = find(parent[target])
    return parent[target]

def union(a,b):
    global parent
    a = find(a)
    b = find(b)

    if a != b:
        if a > b:
            parent[a] = b
        else:
            parent[b] = a

def is_same_parent(a,b):
    return find(a) == find(b)

def set_candidate_bridge():
    candidate_bridge = set()
    for x,y,d in edges:
        start = board[x][y]
        length = 0
        while True:
            x += dx[d]
            y += dy[d]
            if boundaray_validator(x,y):
                end = board[x][y]
                if end != 0:
                    if start != end and length >= 2:
                        candidate_bridge.add((start,end,length))
                    break
                length += 1
            else:
                break

    candidate_bridge = sorted(candidate_bridge, key=lambda x:x[2])
    return candidate_bridge
def set_area_num():
    num = 2
    for x in range(n):
        for y in range(m):
            if board[x][y] == 1:
                bfs(x,y,num)
                num += 1
    return num
def bfs(sx,sy,num):
    global board,edges
    q = deque([(sx,sy)])
    board[sx][sy] = num

    while q:
        x,y = q.pop()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if boundaray_validator(nx,ny):
                if board[nx][ny] == 1:
                    board[nx][ny] = num
                    q.appendleft((nx,ny))
                elif board[nx][ny] == 0:
                    edges.append((x,y,d))
def boundaray_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    return True

solv()