BOJ 17472(다리 만들기 2)풀이

solved.ac 티어 : 골드 3

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

이 문제는 각 섬들마다 다리를 이어서 모든 섬을 오갈 수 있게 하면서 다리의 길이가 최소가 되게 해야 된다. 이때

다리의 길이를 두 점의 가중치로 생각하면 최소 스패닝 트리가 된다.

이제 입력을 dfs으로 탐색해서 섬을 나누고 다리를 이은 다음 최소 스패닝 트리를 구해주면 된다.

 

 

import sys
sys.setrecursionlimit(10**9)
a,b=map(int,input().split())
l=[list(map(int,input().split())) for i in range(a)]
ch=[[0 for i in range(b)]for g in range(a)]
dy=[-1,0,1,0]
dx=[0,1,0,-1]
def dfs(y,x,v):
    ch[y][x]=v
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or nx>=b or ny<0 or ny>=a:
            continue
        if ch[ny][nx]==0 and l[ny][nx]==1:
            dfs(ny,nx,v)
vc=0
for i in range(a):
    for g in range(b):
        if l[i][g]==1 and ch[i][g]==0:
            vc+=1
            dfs(i,g,vc)
ck=[0]*(vc+1)
bc=0
e=[]
for i in range(a):
    val=[0,0]
    for g in range(b):
        if ch[i][g]!=0:
            if val[0]!=ch[i][g] and val!=[0,0]:
                if g-val[1]-1>1:
                    e.append([g-val[1]-1,val[0],ch[i][g]])
                    if ck[val[0]]==0:bc+=1
                    if ck[ch[i][g]]==0:bc+=1
                    ck[val[0]]=1
                    ck[ch[i][g]]=1
            val=[ch[i][g],g]
for g in range(b):
    val=[0,0]
    for i in range(a):
        if ch[i][g]!=0:
            if val[0]!=ch[i][g] and val!=[0,0]:
                if i-val[1]-1>1:
                    e.append([i-val[1]-1,val[0],ch[i][g]])
                    if ck[val[0]]==0:bc+=1
                    if ck[ch[i][g]]==0:bc+=1
                    ck[val[0]]=1
                    ck[ch[i][g]]=1
            val=[ch[i][g],i]
#print(bc)
#for i in range(a):
#    for g in range(b):
#        print(ch[i][g],end=" ")
#    print()
#print(e)
#print(bc,vc)
if bc!=vc:print(-1);sys.exit()
def find(a):
    if uf[a]<0:return a
    uf[a]=find(uf[a])
    return uf[a]
def merge(a,b):
    a=find(a)
    b=find(b)
    if a==b:return 0
    uf[b]=a
    return 1
e.sort()
rt=0
cnt=0
uf=[-1]*(vc+1)
m=len(e)
gh=0
for i in range(m):
    if merge(e[i][1],e[i][2]):
        rt+=e[i][0]
        cnt+=1
        if cnt==vc-1:gh=1;break
if gh==1:print(rt)
else:print(-1)