다리 만들기2(백준 17472)

MST를 만드는 것도 중요하지만 그 전에 입력받은 섬들 간의 만들 수 있는 다리들을 구하는 것이 더 중요하다. 

섬 하나하나의 좌표에 대해서 4방향에 대해서 모두 도달 가능한 다른 섬을 찾아야 하는 과정이 필요하다. 

 

처음에는 섬인 좌표들 중에서 x혹은 y 좌표가 같은 경우에만 계산하려 하니 다시 수정하기가 어려웠다. 

 

#틀린코드
import sys 
from collections import deque 
input =sys.stdin.readline 
def find(a) :
    if a!= parent[a] :
        parent[a] = find(parent[a]) 
    return parent[a]
def union(a,b) :
    if a >=b :
        parent[a] = b 
    else :
        parent[b] = a 
def islandcheck(x,y,mark ):
    q= deque() 
    island_arr[x][y] = mark 
    islandindex.append((mark,x,y))
    q.append((x,y)) 
    while q :
        x,y = q.popleft() 
        for i in range(4) :
            nx,ny =x+dx[i] , y+dy[i] 
            if 0<=nx< n and 0<=ny< m and island_arr[nx][ny]==0 and gra[nx][ny]==1:
                q.append((nx,ny)) 
                island_arr[nx][ny] = mark
                island_pos[mark].append((nx,ny))
                islandindex.append((mark,nx,ny))
    
    
    
    
n,m = map(int, input().split())
gra = []
edges =[] # 가능한 길을 저장하기 
island_arr = [[0 for i in range(m)]for j in range(n)] #각각의 섬에 번호 부여됨
island_pos = [[]for i in range(7)]
islandindex= []
for i in range(n) :
    oneline = list(map(int, input().split()))
    gra.append(oneline) 
# print(gra)
dx = [1,-1,0,0]
dy = [0,0,1,-1]
islandcnt =1 
for i in range(n):
    for j in range(m):
        if gra[i][j] ==1 and island_arr[i][j] ==0 :
            islandcheck(i,j,islandcnt)
            islandcnt += 1 

parent = [i for i in range(islandcnt)]
for i in range(len(islandindex)-1) :
    for j in range(i, len(islandindex)) :
        
        if islandindex[i][0] != islandindex[j][0] and islandindex[i][1]== islandindex[j][1] and abs(islandindex[i][2]-islandindex[j][2])>=3:
            edges.append((abs(islandindex[i][2]-islandindex[j][2])-1, islandindex[i][0], islandindex[j][0])) 
        elif islandindex[i][0] != islandindex[j][0] and islandindex[i][2]== islandindex[j][2] and abs(islandindex[i][1]-islandindex[j][1])>=3:
            edges.append((abs(islandindex[i][1]-islandindex[j][1])-1, islandindex[i][0], islandindex[j][0])) 
edges= set(edges)
edges = list(edges)
edges.sort()
print(island_arr)
print(parent)
print(edges)
ans =0 

for edge in edges :
    cost  = edge[0]
    a,b = edge[1], edge[2] 
    fa,fb = find(a),find(b)
    if fa== fb :
        continue 
    else :
        union(fa,fb) 
        ans+= cost
print(cost)