백준 23743번 : 방탈출

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

23743번: 방탈출

 

 

 

 

 

문제

• 1번부터 N번까지 총 N개의 방
• 각 방에는 친구들이 한 명씩 들어가 있고, 모든 방은 외부로부터 완전히 독립되었음
• 워프 : 최대 M개, i번째 워프 설치하는 데 Ci 시간, ai번과 bi번 방 사이 이동
• 비상탈출구 : i번 방에 설치하는 데 ti 시간
• 비상탈출구의 설치 작업을 동시에 여럿 진행할 수 없음
• 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간 구하기

 

 

예제 입출력

3 3
1 2 2
2 3 2
3 1 2
3 3 3

 

결과 : 7

 

 

 

 

 

 

풀이

• 탈출구를 0번방으로 간주한다 (탈출구로 가는 길도 하나의 간선이다)

 

• MST(최소 스패닝 트리) 알고리즘 중 하나인 크루스칼 알고리즘을 사용했다.
  • 간선 정보(정점1, 정점2, 비용) 저장 → 비용 낮은 순으로 오름차순 정렬
  • 낮은 비용부터 사이클이 존재하지 않게 선택
  • union, find 수행
    • union : 부모가 같은지 확인(사이클인지) → 다르면 부모 갱신(연결)
    • find : 해당 정점의 부모 찾기
  • (정점 개수 - 1) 만큼 선택했으면 종료

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class b23743 {
	static int N, M;
	static Edge[] edgeList;
	static int[] parents;
	
	static class Edge implements Comparable<Edge> {
		int from, to, weight;

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

		@Override
		public int compareTo(Edge o) {
			return this.weight - o.weight;
		}
	}
	
	static void make() {
		parents = new int[N + 1];
		
		for(int i = 0; i < N + 1; i++) {
			parents[i] = i;
		}
	}
	
	static int find(int a) {
		if(parents[a] == a) return a;
		
		return parents[a] = find(parents[a]);
		
	}
	
	static boolean union(int a , int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if(aRoot == bRoot) return false;
		
		parents[bRoot] = aRoot;
		return true;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken()); //방의 개수
		M = Integer.parseInt(st.nextToken()); //설치할 수 있는 워프의 개수
		
		edgeList = new Edge[M + N]; //간선 배열
		
		//워프 연결
		for(int i = 0; i < M; i ++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
		
			edgeList[i] = new Edge(a, b, c);
		}
		
		//탈출구 설치
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 1; i <= N; i ++) {
			int t = Integer.parseInt(st.nextToken());
			edgeList[M + i - 1] = new Edge(0, i, t); //탈출구는 0
		}
		
		//처리
		make(); //부모 노드 만들기
		Arrays.sort(edgeList); //시간 낮은 순 오름차순 정렬
		
		//크루스칼 알고리즘
		int result = 0;
		int count = 0;
		for(Edge edge : edgeList) { //낮은 비용부터 연결
			if(union(edge.from, edge.to)) { //사이클이 존재하지 않으면 간선 선택
				result += edge.weight; //비용 갱신
				if(++count == N) break; //정점 개수 - 1 만큼 선택했으면 종료 : N + 1(탈출구 포함) - 1
			}
		}
		
		//출력
		System.out.println(result);
	}

}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 크루스칼 알고리즘을 오랜만에 공부했다