백준(1197,1414)

최소비용신장트리를 통한 문제해결

최소스패닝트리(1197)

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

• 입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

• 입출력 예시

3 3
1 2 1
2 3 2
1 3 3

--------------

3

해결책

최소비용신장트리를 구성해 해결할 수 있는 문제이다. MST를 구현하기 위해 Union Find를 활용하고, 노드간의 비용을 오름차순 정렬해서 유지하기 위한 우선순위큐를 사용하면 쉽게 해결 할 수 있다.

모든 노드가 연결(즉 직접적이든 간접적이든)되려면 최소 노드개수-1의 간선이 필요하기때문에, 이를 반복문의 조건으로 설정하여 루프를 돌리고, 사이클이 일어나지 않는다면 채택하고 노드간의 비용을 누적하며 진행한다.

코드

import sys
import heapq
from heapq import heappush, heappop

def union(a,b):
    global parent
    ca=find(a)
    cb =find(b)

    if ca>cb :
        parent[ca]=cb
    elif ca < cb :
        parent[cb]=ca
  

def find(node):
    global parent

    if parent[node] ==node:
        return node
    else :
        parent[node]=find(parent[node])
        return parent[node]
    
    

input = sys.stdin.readline

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

parent=[-1]*(n+1)

for i in range(len(parent)):
    parent[i]=i

heap = []

for i in range(m):
    s,e,w = map(int, input().split())
    heappush(heap,[w,s,e])
ans =0

use=0

while heap:
    pnode=heappop(heap)
    

    a=find(pnode[1])
    b=find(pnode[2])
    if a!=b:
        
        union(pnode[1],pnode[2])
        ans+=pnode[0]
        use+=1
    

print(ans)

불우이웃돕기(1414)

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

• 입력

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

• 입출력 예시

3
abc
def
ghi

--------------

40

해결책

전체 3대의 컴퓨터에 대해서 나올 수 있는 모든 조합에 랜선이 연결되었다고 본다. 하지만, 한대만 인터넷에 연결되어있고, 나머지는 연결되어있는 한대에 종속되어도 인터넷이 되기때문에 이문제의 핵심은 최소비용으로 인터넷을 연결할 수 있는 랜선길이를 구하고, 전체 랜선길이에서 차를 구해주면 된다.

1. 일단 입력값이 정수가 아닌 문자로들어오기에, 이를 적절히 변환시켜줘야한다. 문제의 조건을 보면 알 수 있듯이 소문자와 대문자가 서로 다른 숫자범위안에 있기때문에, 아스키코드로 변환 후 적절한 값을 빼줘서 맞춰주도록한다.
2. 랜선의 값이 알파벳대신 0이 들어가있다면 그구간엔 랜선이 없는것이기 때문에, 처리하지 않고, 그외에 것들에 대해 랜선길이를 기준으로 오름차순되어 우선순위큐를 구성할 수 있도록, push시켜준다.
3. 위의 문제와 동일하게 채택간선==노드개수-1 까지 반복하면서 비용을 구하고 전체랜선길이에서 빼준다.

코드

import heapq
import sys
from heapq import heappush, heappop
input=sys.stdin.readline

n = int(input())

parent = [n for n in range(0,n)]

sums=0

def find(a):
    global parent
    
    if parent[a]==a :
        return a
    else :
        parent[a]=find(parent[a])
        return parent[a]
def union(a,b):
    global parent
    ax=find(a)
    bx=find(b)
    if ax<bx :
        parent[bx]=ax
    else:
        parent[ax]=bx

heap = []
for i in range(n):
    s = list(input())
    for j in range(n) :
        if s[j]=='0':
            
            s[j]=0
        else :    
            
            if ord('a')<=ord(s[j]) and ord(s[j])<=ord('z'):
                s[j]=ord(s[j])-96
                
            elif ord('A')<=ord(s[j]) and ord(s[j])<=ord('Z'):
                s[j] = ord(s[j])-38
            sums=sums+s[j]
            if i==j:
                continue
            heappush(heap,[s[j],i,j])
            
           
used = 0

cost=0

while heap:
    pnode=heappop(heap)
    pa = find(pnode[1])
    pb = find(pnode[2])
    if pa != pb:
        union(pnode[1],pnode[2])
        used+=1
        cost+=pnode[0]

if used == n-1 :
    
    print(sums-cost)
else :
    print(-1)