최소 신장 트리 예제 - 3
문제 분석
인접 행렬의 형태로 데이터가 들어오기 때문에 이 부분을 최소 신장 트리가 가능한 형태로 변형하는 것이 이 문제의 핵심이다.
먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다.
이때 i와 j가 같은 값은 같은 컴퓨터를 연결한다는 의미이므로 넘어가고, 나머지 위치의 값들을
i -> j로 가는 에지로 생성하고, 에지 리스트에 저장하면 최소 신장 트리 문제로 변형할 수 있다.
손으로 풀어보기
입력 데이터의 정보를 리스트에 저장한다. 먼저 입력으로 주어진 문자열을 숫자로 변홚해 총합으로 저장한다. 소문자는
현재 문자 - 'a' + 1, 대문자는현재 문자 - 'A' + 27로 변환한다. i와 j가 다른 경우에는 다른 컴퓨터를 연결하는 랜선이므로 에지 리스트에 저장한다.저장된 에지 리스트를 바탕으로 최소 신장 트리 알고리즘을 수행한다.
최소 신장 트리에서 사용한 에지 개수가
노드 개수 - 1개면 처음 저장해 둔 랜선 길이의 총합에서 최소 신장 트리의 결괏값을 뺀 값을 출력하면 된다. 사용한 에지 개수가노드 개수 - 1개가 아니면 -1을 출력한다.
슈도코드
n(노드 개수)
pq(우선순위 큐)
sum(랜선의 합)
for n 반복:
한 줄씩 입력
for n 반복:
if 소문자:
현재 문자 - 'a' + 1
elif 대문자:
현재 문자 - 'A' + 27
sum에 현재 랜선 길이 더하기
if i와 j가 다르고 연결 랜선이 있다면:
랜선 정보 큐 저장
parent(대표 노드 저장 리스트)
find(a):
a가 대표 노드면 리턴
아니면 a의 대표 노드값을 find(parent[a])값으로 저장
union(a, b):
a와 b의 대표 노드 찾기
두 원소의 대표 노드끼리 연결
useEdge(엣지 사용 횟수 변수)
result(정답 변수)
while 사용한 엣지의 횟수가 노드 개수 - 1이 될 때까지:
큐에서 에지 정보 가져오기
if 에시 시작점과 끝점의 부모 노드가 다르면:
union 연산 수행
에지의 가중치를 정답에 더하기
엣지 사용 횟수 1 증가
if 사용한 에지가 노드-1 만큼:
sum - result 출력
else:
-1 출력코드 구현 - 파이썬
import sys
from queue import PriorityQueue
input = sys.stdin.readline
n = int(input())
pq = PriorityQueue()
sum = 0
for i in range(n):
data = list(input())
for j in range(n):
temp = 0
if 'a' <= data[j] <= 'z':
temp = ord(data[j]) - ord('a') + 1 # ord(): 유니코드를 정수로 반환
elif 'A' <= data[j] <= 'Z':
temp = ord(data[j]) - ord('A') + 27
sum += temp
if i != j and temp != 0:
pq.put((temp, i, j))
parent = [0] * n
for i in range(n):
parent[i] = i
def find(a):
if parent[a] == a:
return a
parent[a] = find(parent[a])
return parent[a]
def union(a, b):
a = find(a)
b = find(b)
if a != b:
parent[b] = a
useEdge = 0
result = 0
while pq.qsize() > 0:
v, s, e = pq.get()
if find(s) != find(e):
union(s, e)
result += v
useEdge += 1
if useEdge == n - 1:
print(sum - result)
else:
print(-1)코드 구현 - 자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
//가중치 기준으로 오름차순 정렬하는 에지 정보 클래스
static class Edge implements Comparable<Edge>{
int start, end, dist;
public Edge(int start, int end, int dist) {
this.start = start;
this.end = end;
this.dist = dist;
}
@Override
public int compareTo(Edge o) {
return this.dist - o.dist;
}
}
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue<Edge> pq = new PriorityQueue<>();
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int sum = 0;
for (int i = 0; i < n; i++) {
String input = br.readLine();
for (int j = 0; j < n; j++) {
int temp = 0;
char ch = input.charAt(j);
if ('a' <= ch && ch <= 'z') {
temp = ch - 'a' + 1 ;
} else if ('A' <= ch && ch <= 'Z') {
temp = ch - 'A' + 27;
}
sum += temp;
if (i != j && temp != 0) {
pq.add(new Edge(i, j, temp));
}
}
}
int useEdge = 0;
int result = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int start = edge.start;
int end = edge.end;
int len = edge.dist;
if (find(start) != find(end)) {
union(start, end);
result += len;
useEdge++;
}
}
if (useEdge == n - 1) {
System.out.println(sum - result);
} else {
System.out.println(-1);
}
}
private static int find(int a) {
if (parent[a] == a) {
return a;
}
return parent[a] = find(parent[a]);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
}Last updated