[백준 알고리즘] 1922 네트워크 연결(with Java)

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

최소 비용으로 모든 컴퓨터를 네트워크로 연결하는 방법을 찾는 문제이다.

문제의 알고리즘 분류에도 나와 있듯

이 문제는 '최소 스패닝 트리', '최소 신장 트리' 문제이다.

최소 스패닝 트리 문제를 해결하는 알고리즘으로

프림 알고리즘과 크루스칼 알고리즘이 있다.

각 알고리즘에 대한 자세한 설명은 아래의 링크를 참조한다.

프림 알고리즘(Prim's algorithm)

크루스칼 알고리즘(Kruskal’s algorithm)

그리고 나는 이 문제를 프림 알고리즘을 적용하여 해결하였다.

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int rslt = 0; // 컴퓨터의 수 int N = Integer.parseInt(br.readLine()); // 간선의 수 int M = Integer.parseInt(br.readLine()); int[][] map = new int[N+1][N+1]; for(int i = 0; i < M; i++) { String line = br.readLine(); String[] sec = line.split(" "); int s = Integer.parseInt(sec[0]); // start int e = Integer.parseInt(sec[1]); // end int c = Integer.parseInt(sec[2]); // cost map[s][e] = map[e][s] = c; } // passed computer int[] passedComputer = new int[N]; passedComputer[0] = 1; int passedComputerCnt = 1; while(passedComputerCnt < N) { int min = Integer.MAX_VALUE; int minComputerFrom = 0; int minComputerTo = 0; for(int i = 0; i < passedComputerCnt; i++) { for(int j = 1; j <= N; j++) { if(map[passedComputer[i]][j] < min && map[passedComputer[i]][j] != 0) { boolean isCycle = false; for(int k = 0; k < passedComputerCnt; k++) { if(passedComputer[k] == j) { isCycle = true; map[passedComputer[i]][j] = 0; map[j][passedComputer[i]] = 0; break; } } if(!isCycle){ min = map[passedComputer[i]][j]; minComputerFrom = passedComputer[i]; minComputerTo = j; } } } } passedComputer[passedComputerCnt] = minComputerTo; passedComputerCnt++; rslt = rslt + min; } // 결과출력 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write(rslt+"\n"); bw.flush(); } // end of main method }