[Baekjoon] 17472번 : 다리 만들기 2 (Python, 최소 신장 트리)

[Baekjoon] 17472번 : 다리 만들기 2 (Python, 최소 신장 트리)

 

목차

 

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

17472번: 다리 만들기 2

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 30840KB / 시간 68ms / 코드 길이 1886B

 

본 문제는 크게 3단계로 구분할 수 있다.

1) DFS, BFS로 나라 index를 선정하고 좌표에 대한 값을 저장한다.

2) 저장한 좌표와 나라 index를 기반으로 나라 간 거리를 구한다. 구한 거리를 비용으로 생각하는 간선을 설정한다.

3) 구한 거리를 정렬하고 이를 최소 신장 트리를 기반으로 크루스칼 혹은 프림 알고리즘을 적용한다.

 

개인적으로 까다로웠던 부분은 2) 거리를 구하는 부분으로 종횡에 대한 축 방향에 따른 거리 계산이었다. 이에 대한 다양한 함수를 구축할 수 있었으나 개인적으로 가장 쉽다고 생각하는 방법을 통해 문제를 해결하였다.

 

최소 신장 문제에 대해 많이 풀었다고 해도 이 문제에서는 당황할 수 있다고 판단된다.

시간도 생각보다 훨씬 많이 소모됨.

 

 

import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(i, j, country):
    if i <= -1 or i >= len(arr) or j <= -1 or j >= len(arr[0]):
        return 0
    if visit[i][j] == 0 and arr[i][j]:
        visit[i][j] = country
        ctry_coord.append((i,j,country))
        for k in range(4):
            nx, ny = i+dx[k], j+dy[k]
            dfs(nx, ny, country)
    return 0

def distance():
    for coord in ctry_coord:
        i, j, country_num = coord
        for k in range(4):
            dist=0
            nx, ny = i + dx[k], j + dy[k]

            while True:
                if nx <= -1 or nx >= len(visit) or ny <= -1 or ny >= len(visit[0]):
                    break
                else:
                    if country_num == visit[nx][ny]:
                        break

                    if visit[nx][ny] == 0:
                        nx, ny = nx + dx[k], ny + dy[k]
                        dist += 1
                        continue

                    if dist < 2:
                        break

                    edges.append((dist, country_num, visit[nx][ny]))
                    break

def f_p(p, x):
    if p[x] != x:
        p[x] = f_p(p, p[x])
    return p[x]

def union(p, a, b):
    a, b = f_p(p, a), f_p(p, b)
    p[max(a,b)] = min(a,b)

n,m = map(int, input().split())

arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

visit = [[0]*m for i in range(n)]
country = 0
ctry_coord = []
edges = []
res = 0

for i in range(n):
    for j in range(m):
        if not visit[i][j] and arr[i][j] == 1:
            country += 1
            dfs(i, j, country)

p = [i for i in range(country+1)]

distance()
edges.sort()
cnt = 0
for edge in edges:
    c, a, b = edge

    if f_p(p, a) != f_p(p, b):
        union(p, a, b)
        res += c
        cnt += 1

if cnt == country-1:
    print(res)
else:
    print(-1)