백준 1922 - 네트워크 연결

Java

1922 번 - 네트워크 연결

문제

컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라
컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.
연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

접근 방법

MST를 만드는 문제이므로, Kruscal과 Prim의 방법으로 각각 풀어보았다.
Prim의 방법이 조금 더 시간이 단축된 문제였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m;
	static long result;
	static int[][] graph;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	m = stoi(br.readLine());
    	
    	graph = new int[n+1][n+1];
    	int a, b, c;
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		c = stoi(stk.nextToken());
    		graph[a][b] = c;
    		graph[b][a] = c;
    	}
    	
    	// prim 알고리즘
    	int[] node = new int[n+1];
    	boolean[] vis = new boolean[n+1];
    	Arrays.fill(node, Integer.MAX_VALUE);
    	node[1] = 0;
    	int curN = -1;
    	for(int idx = 0; idx < n; idx++) {
    		int min = Integer.MAX_VALUE;
    		for(int i = 1; i <= n; i++) {
    			if(!vis[i] && min > node[i]) {
    				min = node[i];
    				curN = i;
    			}
    		}
    		
    		result += min;
    		vis[curN] = true;
    		
    		for(int i = 1; i <= n; i++) {
    			if(!vis[i] && node[i] > graph[curN][i] && graph[curN][i] != 0) {
    				node[i] = graph[curN][i];
    			}
    		}
    	}
    	
    	System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

import java.util.*;
import java.io.*;

public class Main {
	static int n, m;
	static long result;
	static List<Edge> edge;
	static int[] pNode;
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	m = stoi(br.readLine());
    	
    	edge = new ArrayList<>();
    	int a, b, c;
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		c = stoi(stk.nextToken());
    		edge.add(new Edge(a,b,c));
    	}
    	
    	pNode = new int[n+1];
    	init();
    	
    	Collections.sort(edge);
    	
    	int cnt = 0;
    	for(Edge e : edge) {
    		if(union(e.from, e.to)) {
    			result += e.weight;
    			cnt++;
    			if(cnt == n) {
    				break;
    			}
    		}
    	}
    	
    	
    	System.out.println(result);
    	br.close();
	}

	static void init() {
		for(int i = 1; i <= n; i++) {
			pNode[i] = i;
		}
	}
	
	static int findParent(int num) {
		if(pNode[num] == num) {
			return num;
		}
			
		return pNode[num] = findParent(pNode[num]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = findParent(a);
		int bRoot = findParent(b);
		
		if(aRoot == bRoot) {
			return false;
		}
		int min = Math.min(aRoot, bRoot);
		pNode[aRoot] = min;
		pNode[bRoot] = min;
		return true;
	}
	
	static class Edge implements Comparable<Edge>{
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

Knap Sack 문제인 줄 알고, 생각해보다가, 애초에 가능 할 수 없는 문제였다.
최소 O(n^2)이니, 풀 수 없는 문제였으니 미리 알아 챌 필요가 있었다.

개선할 점

없습니다.