BaekJoon 17472번 : 다리 만들기 2 (python)

BaekJoon 17472번 : 다리 만들기 2 (G1 33.169%)

다리 만들기 2 문제

여러가지 구현이 섞이고 섞인 그래프 문제이자 결국엔 크루스칼 알고리즘을 사용하는 문제이다.

• 먼저 2차원 배열로 이루어진 그래프중에서 뭉쳐있는 지역끼리 같은 루트노드로 묶어줘야하기 때문에 for문을 통해 순회하며 BFS를 통해 이어져있는 부분끼리 같은 root노드를 가질 수 있게 작업을 해준다.
• 그렇게 서로다른 root노드끼리 묶어진 부분집합들을 만들었으면 크루스칼 알고리즘을 통한 작업을 하기 위한 거리 계산과 연결 유무를 찾아주어야 한다.
• 해당 문제에서는 다리의 방향이 중간에 바뀌면 안되고 다리의 길이는 2이상이어야 한다고 한다. 이를 통해 같을 열에 있거나 같은 행에 있는 노드들끼리의 연결이라 생각할 수 있고 해당 길이가 2칸 이상이어야 한다는 의미이다.
• 또 다른 부분으로 우리가 연결하려는 다리 중간에 다른 섬이 있으면 해당 다리는 불가능하다는 점도 구현해주어야 한다.
• 이를 통해 우리는 탐색해주며 루트노드가 서로 다르며 행이나 열이 같은 루트 쌍을 찾아준다. 해당 루트 쌍들의 중간에 다른 루트노드들을 거치지않으며 둘을 잇는 다리의 길이가 2이상일 경우 edges에 다리 길이와 루트 노드들을 append해준다.
• 길이를 오름차순으로 정렬하여 크루스칼 알고리즘을 돌려주면 다리의 최소 길이가 나오는데 우리가 다리를 놓아서 만들 수 없는 경우들은 -1을 출력해주어야 한다. 여기서 우리가 다리를 놓아서 만들 수 없는 경우는 root노드가 0으로 모두 같지 않을 경우를 의미하게된다. 이를 위해 각 노드들을 find함수를 통해 루트노드들로 다시 한 번 탐색해주고 해당 루트 노드들이 모두 0으로 되어있을 경우 다리의 최소 길이를 출력하고 하나라도 0으로 되어있지 않을 경우 -1을 출력해준다.

---

import sys
from collections import deque
input = sys.stdin.readline

def bfs(i,j,count) :
    q = deque()
    q.append((i,j))
    check[i][j] = True
    rootisland[i][j] = count
    while q :
        x, y = q.popleft()
        for i,j in [(-1,0),(1,0),(0,-1),(0,1)] :
            nx, ny = x + i, y + j
            if 0<=nx<N and 0<=ny<M and not check[nx][ny] and graph[nx][ny] == 1 :
                check[nx][ny] = True
                rootisland[nx][ny] = count
                q.append((nx,ny))
            
def find(x):
    if root[x] != x:
        root[x] = find(root[x])  # 경로 압축
    return root[x]

def union(x, y):
    rootX = find(x)
    rootY = find(y)
    if rootX < rootY:
        root[rootY] = rootX
    else:
        root[rootX] = rootY

N, M = map(int,input().split())
graph = list()
rootisland = [[-1]*M for _ in range(N)]

for _ in range(N) :
    s = list(map(int,input().split()))
    graph.append(s)

check = [[False]*M for _ in range(N)]
count = 0
for i in range(N) :
    for j in range(M) :
        if graph[i][j] == 1 and not check[i][j]:
            bfs(i,j,count)
            count += 1

root = list(i for i in range(count))

edges = list()
for i in range(N) :
    for j in range(M) :
        if rootisland[i][j] != -1 :
            for k in range(i, N) :
                for l in range(j, M) :
                    if rootisland[k][l] != -1 and rootisland[i][j] != rootisland[k][l] and (i==k or j==l):
                        count = 0
                        if i == k :
                            start = min(j,l)
                            end = max(j,l)
                            for t in range(start+1,end) :
                                if rootisland[i][t] != -1:
                                    count = 1
                        elif j == l :
                            start = min(i,k)
                            end = max(i,k)
                            for t in range(start+1,end) :
                                if rootisland[t][j] != -1 :
                                    count = 1
                        
                        a, b = rootisland[i][j], rootisland[k][l]
                        dist = abs(i-k) + abs(j-l) - 1
                        if dist > 1 and count == 0:
                            edges.append((dist,a,b))

result = 0
edges.sort()

for i in edges :
    cost, x, y = i[0], i[1], i[2]
    if find(x) != find(y) :
        union(x,y)
        result += cost

for i in range(len(root)) :
    find(i)

if root.count(0) != len(root) :
    print(-1)
else :
    print(result)

---