[17472번] 다리 만들기 2

문제 출처 :

 

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

 

 

 

 

알고리즘 분석 :

문제 해결에 필요한 사항

1. 조합

2. 구현

 

다리를 모두 찾아낸 다음에 각 섬과 섬 사이에 최소 거리가 되는 맵을 만들고

 

다리를 섬의 개수 -1개로 골라서 이 섬들이 조건에 맞게 연결이 되는 것들 중 가장 작은 연결 비용이 드는 것이 답이된다.

 

즉, 

1) 각 섬마다 지역 번호를 표시하면서 섬의 테두리를 저장하는 배열을 만든다.
2) 섬의 테두리에서 다른 섬의 테투리까지 다리를 건설하는 비용을 최소로 하는 맵을 만든다
3) 섬의 개수 - 1 개의 다리를 골라 섬들이 모두 연결되는지 판별하고 연결 된다면 가장 작은 연결 비용을 결과에 저장한다

 

이때 사실 최소 스패닝 트리로 문제를 풀어도 되나 제한이 크지 않기에 완전 탐색으로 풀어도 해결이 가능하다.

 

 https://www.crocus.co.kr/733

최소 스패닝 트리(Minimum Spanning Tree, MST)

 

 

 

 

 

소스 코드 : 

 

from collections import deque 
from itertools import combinations 
import sys 
input = lambda: sys.stdin.readline().rstrip() 
sys.stdin = open('input.txt') 

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

m = float('inf') 

# 구역 나누기 
def DFS(x,y,n): 
    D[x][y] = n 
    for i in range(4): 
        nx = x + dx[i] 
        ny = y + dy[i] 
        if 0 <= nx < N and 0 <= ny < M and not C[nx][ny]: 
            if D[nx][ny]: 
                C[nx][ny] = 1 
                D[nx][ny] = n 
                DFS(nx,ny,n) 
            else: 
                E[x][y] = 1 

def Cost(x,y): 
    pos = D[x][y] 
    for i in range(4): 
        cnt = 0 
        cx = x 
        cy = y  
        while 1: 
            cx = cx + dx[i] 
            cy = cy + dy[i] 
            if 0 <= cx < N and 0 <= cy < M and not D[cx][cy]: 
                cnt += 1 
            else: 
                break 
        if 0 <= cx < N and 0 <= cy < M and D[cx][cy] != pos and cnt >= 2: 
            npos = D[cx][cy] 
            P[pos][npos] = P[npos][pos] = min(cnt,P[pos][npos]) 


def connect(n, v): 
    global m 
    if n == size: 
        if sum(check) == section-1: 
            if BFS(1,0): 
                m = min(m,v) 
                return 
            else: 
                return 
        else: 
            return 

    cost, land1, land2 = data[n]  
    if not visited[n]: 
        visited[n] = 1 
        check[land1] = 1 
        check[land2] = 1 
        connect(n+1,v+cost) 

def BFS(x,depth): 
    V = [0]*(section) 
    V[x] = 1 
    queue = deque() 
    queue.append(x) 

    while queue: 
        q = queue.popleft() 
        for w in Graph[q]: 
            if not V[w]: 
                V[w] = 1 
                queue.append(w) 
     
    if sum(V) == section-1: 
        return True 
    return False 


if __name__ == "__main__": 
    N, M = map(int,input().split()) 
    D = [list(map(int,input().split())) for _ in range(N)] 
    C = [[0]*M for _ in range(N)] 
    E = [[0]*M for _ in range(N)] 
    Possible = True 
    result = 0 
     
    # 구역 나누기 
    section = 1 
    for i in range(N): 
        for j in range(M): 
            if D[i][j] and not C[i][j]: 
                DFS(i,j,section) 
                section += 1 

    # 최소 다리 비용, 연결 확인 
    P = [[float('inf')]*section for _ in range(section)] 
    for i in range(N): 
        for j in range(M): 
            if E[i][j]: 
                Cost(i,j) 

    # 조합으로 비용 무한대를 제외하고 섬 두개 선택 
    array = list() 
    for combi in combinations(range(1,section),2): 
        x, y = combi 
        if P[x][y] != float('inf'): 
            array.append([P[x][y],x,y]) 

    if not array: 
        Possible = False 
    else: 
        combi_array = list() 
        size = section-2 
        for combi in combinations(array,size): 
            Graph = [[] for _ in range(section)] 
            for location in combi: 
                val, u, v = location 
                Graph[u].append(v) 
                Graph[v].append(u) 
            visited = [0]*len(array) 
            check = [0]*section 
            data = list(combi) 
            connect(0,0) 
    if Possible: 
        if m == float('inf'): 
            print(-1) 
        else: 
            print(m) 
    else: 
        print(-1)
        
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>