×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,488,524명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)

문제 출처 :

 

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

 

 

 

 

알고리즘 분석 :


문제 해결에 필요한 사항

1. 조합

2. 구현

 

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

 

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

 

즉, 

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

 

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

 

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

 

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

목록 1. 최소 스패닝 트리(Minimum Spanning Tree, MST)란? 2. 최소 스패닝 트리(Minimum Spanning Tree, MST) 알고리즘- Kruskal's Algorithm 3. Kruskal's Algorithm Source Code 4. 최소 스패닝 트리(Minimum S..

www.crocus.co.kr

 

 

 

 

 

소스 코드 : 

 
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 >>

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1018번] 체스판 다시 칠하기  (0) 2020.03.16
[17472번] 다리 만들기 2  (0) 2020.03.14
[SwExpertAcademy] 아나그램  (0) 2020.01.04
[17142번] 연구소 3  (0) 2019.12.27
[SwExpertAcademy] Pole  (0) 2019.12.18
[SwExpertAcademy] 최대 부분 배열  (0) 2019.11.06