알고리즘/그래프

백준_전기가부족해_10423_Prim&Kruskal

ganzii 2021. 1. 11. 19:11

문제 링크

조건

  •  N  : 도시 개수, 1~1000
  •  M  : 간선 개수(설치 가능한 케이블 수), 1~100,000
  •  K  : 발전소 도시 개수, 1~N

접근 방법

  1. Kruskal
    • PriorityQueue에 가능한 모든 간선 넣음
    • PriorityQueue에서 가장 짧은 간선(가장 싼 케이블) 가져와 해당 노드를 MST에 포함시킴
      • 조건 : 사이클을 생성하거나 이미 발전소와 연결되어 있지 않은 경우만 MST에 포함
  2. Prim
    • city[] : 각 도시까지의 최단거리를 저장할 배열(MST에 노드가 하나 씩 포함될 때마다 값 갱신)
    • 모든 도시가 발전소와 연결될 때 까지 - while(cnt < N) - 매번 최소 간선 찾아 연결하고 city 배열을 갱신해줌

솔루션

  1. Kruskal 
    public class Main {//Kruskal

	static int N,M,K;//도시 개수 N, 케이블 설치 가능 개수 M, 발전소 개수 K
	static int[] parent;//사이클 확인
	static boolean[] check;//발전소 연결 확인
	static boolean[][] cable;//케이블 연결된 도시 체크
	static int city;
	static class Distance implements Comparable<Distance>{
		int s, e, d;
		Distance(int s, int e, int d){
			this.s = s;
			this.e = e;
			this.d = d;
		}
		
		@Override
		public int compareTo(Distance dis) {
			return Integer.compare(this.d, dis.d);
		}
	}
	static PriorityQueue<Distance> pq;
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("input/bj/10423_전기가부족해.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		
		parent = new int[N+1];
		check = new boolean[N+1];
		cable = new boolean[N+1][N+1];
		for(int i = 1; i < N+1; i++) {//부모노드 자기자신으로 설정
			parent[i] = i;
		}
		
		String[] plant = br.readLine().trim().split(" ");
		for(int i = 0; i < K; i++) {//발전소 도시 체크
			check[Integer.parseInt(plant[i])] = true;
		}

		pq = new PriorityQueue<Distance>();
		
		for(int i = 0; i < M; i++) {//도시끼리 케이블 설치 비용 저장
			st = new StringTokenizer(br.readLine().trim(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			pq.add(new Distance(s,e,d));
		}
		
		
		city = K;//발전소 연결 된 도시 개수
		int answer = 0;
		while(city < N) {//모든 도시가 발전소에 연결될때까지
			Distance cur = pq.poll();
			int sp = findSet(cur.s);
			int ep = findSet(cur.e);
			
			if(sp == ep) continue;//사이클 생성
			
			if(check[sp] && check[ep]) continue;//이미 발전소 연결되어 있으면
			
			parent[sp] = ep;
			cable[cur.s][cur.e]= cable[cur.e][cur.s] = true;//케이블 설치 체크 
			answer += cur.d;
			
			//sp와 ep 둘 중 한 그룹만 발전소 연결이 되어 있는 경우
			if(check[sp]) {
				dfs(cur.s);
			}else if(check[ep]) {
				dfs(cur.e);
			}
			
		}
		
		System.out.println(answer);
		
	}
	
	private static void dfs(int sp) {
		for(int i = 1; i < N+1; i++) {
			if(!cable[sp][i]) continue;//케이블X
			if(check[i]) continue;//발전소 이미 연결 되어 있음
			
			check[i] = true;
			city++;//발전소에 연결된 도시
			dfs(i);
		}
	}

	public static int findSet(int node) {
		if(node == parent[node]) {
			return node;
		}
		
		return parent[node] = findSet(parent[node]);
	}
}
  2. Prim 
    public class Main {//Prim

	static int N,M,K;//도시 개수 N, 케이블 설치 가능 개수 M, 발전소 개수 K
	static boolean[] check;//발전소 연결 확인
	static int[][] cable;//케이블 연결된 도시 체크
	static class City implements Comparable<City>{
		int num, cost;
		City(int num, int cost){
			this.num = num;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(City c) {
			return Integer.compare(this.cost, c.cost);
		}
	}
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("input/bj/10423_전기가부족해.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		
		check = new boolean[N+1];
		cable = new int[N+1][N+1];
		
		String[] plant = br.readLine().trim().split(" ");
		
		for(int i = 0; i < M; i++) {//도시끼리 케이블 설치 비용 저장
			st = new StringTokenizer(br.readLine().trim(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			cable[s][e] = cable[e][s] = d;
		}
		
		City[] city = new City[N+1];//각 도시까지 최단거리 저장할 배열
		for(int i = 1; i < N+1; i++) {
			city[i] = new City(i, Integer.MAX_VALUE);//최초에 최대값으로 세팅
		}
		
		for(int i = 0; i < K; i++) {//발전소 도시 체크
			int cur = Integer.parseInt(plant[i]);
			city[cur].cost = 0;//발전소 도시는 cost 0
		}
		
		int cnt = 0;//발전소 연결 된 도시 개수
		int answer = 0;//총 비용
		
		while(cnt < N) {
			int min = Integer.MAX_VALUE;
			int idx = -1;
			for(int i = 1; i < N+1; i++) {//최소 간선 찾기
				if(check[i]) continue;//이미 발전소 연결됐으면 continue
				if(city[i].cost < min) {
					min = city[i].cost;
					idx = i;
				}
			}
			if(idx == -1) break;//더 이상 연결할 도시 없으면 break;
			City cur = city[idx];
			
			
			int next = cur.num;
			check[next] = true;
			cnt++;
			answer += cur.cost;
			
			for(int i = 1; i < N+1; i++) {//각 도시까지 최단거리 배열 갱신
				if(cable[next][i] == 0) continue;
				
				if(city[i].cost > cable[next][i]) {
					city[i].cost = cable[next][i];
				}
			}
		}
		
		System.out.println(answer);
		
	}
}

리뷰

  • N이 크지 않아서 Prim이나 Kruskal이나 시간이나 메모리 자원은 비슷하게 사용
  • Prim의 경우 노드별 간선이 빽빽하게 있을 경우 유리
  • Kruskal의 경우 노드에 비해 간선의 개수가 적을 때 유리
저작자표시 (새창열림)