백준 | 13424번. 비밀 모임 -다익스트라

⬛ 백준 13424번. 비밀 모임 -다익스트라

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

13424번: 비밀 모임

문제

해리와 친구들은 엄브릿지의 감시를 피해 어둠의 마법 방어술을 연습하기 위한 비밀 모임을 하려고 한다. 그들은 아무도 모르게 모임의 장소를 전달하기 위해 가짜 갈레온을 사용하는데, 해리가 자신의 가짜 갈레온에 모임의 장소를 적으면 친구들이 가진 가짜 갈레온에 해리가 적은 장소가 나타난다. 해리가 다니고 있는 호그와트 마법 학교에는 모임에 사용할만한 N개의 방이 있다. 각 방에는 1부터 N까지 번호가 붙어 있으며 중복된 번호는 없다. 마법 학교답게 N개의 방은 M개의 마법으로 만들어진 비밀통로로 연결되어있다. 모든 비밀통로는 양방향 통행이 가능하며 자연수의 길이를 가진다. 모임에 참여하는 친구들은 총 K명이다.

해리는 N개의 방 중에서 한 곳을 정해 오늘 모임의 장소로 이용하려고 한다. 모임 장소를 정하기 전, 호그와트 비밀지도를 이용해 학교 안에 있는 사람들의 현재 위치를 확인해보니 모임에 참여하는 친구들은 N개의 방 중에서 한군데씩에 각각 위치해 있었다. 불행하게도 호그와트 안에서는 순간이동이 금지되어 있어서 모임에 참여하는 친구들은 들키지 않도록 비밀통로만 이용해서 오늘의 모임 장소로 가려고 한다. 이때 이들은 항상 처음 위치에서 모임 장소까지의 이동 거리가 가장 짧은 경로만을 이용한다. 여기서 ‘이동 거리’란 처음 위치에서 모임 장소까지 가기 위해 이용한 비밀 통로들의 길이의 합을 의미한다. 어느 방을 모임 장소로 사용할까 고민하던 해리는 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용하기로 했다.

위 그래프에서 각 정점에 적힌 숫자는 방의 번호이며, 간선 위의 숫자는 방과 방을 연결하는 비밀통로의 길이이다. 모임에 참석하는 두 친구는 현재 3번, 5번 방에 있다. 만약 오늘 모임의 장소로 2번 방을 이용한다면 3번 방에 있는 친구 A의 가장 짧은 경로는 3번-2번 방 순이며 이동 거리는 2가 된다. 5번 방에 있는 친구 B의 경우 2번 방으로 가는 가장 짧은 경로는 5번-1번-3번-2번 방 순이며 이동 거리는 5가 된다. 이때, 두 친구의 이동 거리의 총합은 7이 된다. 그러나 만약 1번 방을 모임 장소로 선택한다면, 친구 A의 이동 거리는 1이 되며, 친구 B의 이동 거리는 2가 되어, 두 친구의 이동 거리의 총합은 3이 된다. 위 예시에서는 1번, 3번, 또는 5번 방을 오늘 모임의 장소로 이용했을 때 친구들의 이동 거리의 총합이 3으로 최소가 된다.

해리가 오늘의 모임 장소를 가짜 갈레온에 적으면 모임에 참여하는 K명의 친구는 그 사실을 즉시 알게 되며, 현재 하던 일을 모두 중단하고, 바로 오늘의 모임 장소로 이동한다. 해리를 위해 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소를 찾아 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방의 개수 N (2 ≤ N ≤ 100), 비밀통로의 개수 M(N-1 ≤ M ≤ N(N - 1)/2)이 공백으로 구분되어 주어진다. 그 다음 줄부터 M개의 줄에 걸쳐 비밀통로의 정보(a, b, c)가 주어진다. a와 b는 비밀통로로 연결된 두 방의 번호이며 c는 a와 b를 연결하는 비밀통로의 길이이다. a와 b는 항상 다르며 c는 1 이상 1,000 이하의 자연수이다. 두 방을 연결하는 비밀통로는 반드시 하나씩만 존재한다. 또한 어떤 방에서 다른 방으로 비밀통로를 이용해서 갈 수 없는 경우는 존재하지 않으며, 같은 비밀통로에 대한 정보가 중복되어 주어지지 않는다. 비밀통로의 정보가 모두 주어진 다음 그 다음 줄에 모임에 참여하는 친구의 수 K(1 ≤ K ≤ N)가 주어진다. 각 테스트 케이스의 마지막 줄에는 모임에 참여하는 친구들이 현재 위치해 있는 방의 번호 K개가 공백으로 구분되어 주어진다. 친구들이 있는 방은 항상 N개의 방 중 하나이며, 방 번호가 중복되는 경우는 없다. 즉, 두 명 이상이 한 방에 있는 경우는 입력으로 주어지지 않는다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 각 테스트 케이스의 답을 순서대로 1줄에 1개씩 출력한다. 각 테스트 케이스마다 모임에 참여하는 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소의 방 번호를 출력한다. 만약 그러한 장소가 여러 개일 경우, 그중 번호가 가장 작은 방의 번호를 출력한다.

💚나의 풀이

• K명의 친구들이 존재하는 각 위치를 시작 위치로 하여 다익스트라 함수를 호출했다.
• result[K][N+1] 배열을 따로 만들어서, 각 K번째 친구의 위치에서 다른 정점으로 나아가는 최단거리를 저장시킬 수 있게 만들었다.

//고민 : K가 고정이 아닌데 도대체 어떻게 ? 하지 ???? 

int K =kb.nextInt();//친구 명수 
//2차원 배열을 만들자/
int[][] result = new int[K][N+1];//각 시작점 k에 대한 배열 되도록

for(int i=0; i<K; i++) {
	//각각의 친구가 시작값이 되어야 하는데.
	int st = kb.nextInt();
	//임시 배열 
	int[] dist = dijkstra(st);
	
	for(int j=1; j<= N; j++) {//결과를 각 i행에 대한 j열의 배열로 담기 
		result[i][j] = dist[j];//연달아 담아두고.
	}
}

 

• 또한, 각각의 정점끼리의 distance 합을 구해서 그들 중 min 값을 갖는 정점을 약속장소로 만들어야 하므로.
• 바깥 for문을 열로 칭하고, 안쪽 for문을 행으로 칭할 수 있게 하여, 각각의 열별로 누적 합을 구하고 min값을 찾았다.

int min = Integer.MAX_VALUE;//최대값으로 세팅해두고 
//답 세팅해야 하잖아

for(int i=1; i<=N; i++) { //각각의 열에 대한 
	int sum = 0;//각 행별 합
	for(int k=0; k<K; k++) {//행 끼리 합
		sum += result[k][i]; //행끼리 누적 
	}
	min = Math.min(min, sum);//가장 작은 합을가진 애가 min 값이다. 
}

최종 코드

package to_0831_6;

import java.util.*;
import java.util.Scanner;

/*13424번. 비밀 모임- 다익스트라 문풀 */
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e= e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int T;
	static int N;//방개수 
	static int M;//간선 개수 
	static ArrayList<ArrayList<Edge>> graph;
	
	//다익스트라 
	static int[] dijkstra(int st) {//시작정점 따라서 
		int[] dist = new int[N+1];
		Arrays.fill(dist, Integer.MAX_VALUE);//초기화 
		boolean[] visited = new boolean[N+1];
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		//시작점 처리 
		dist[st] = 0;
		pQ.offer(new Edge(st, 0));
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(visited[cur.e]) continue;
			visited[cur.e] = true;
			
			for(Edge nx : graph.get(cur.e)) {
				if(!visited[nx.e] && dist[nx.e] > dist[cur.e] + nx.val ) {
					dist[nx.e] = dist[cur.e] + nx.val;
					pQ.offer(new Edge(nx.e, dist[nx.e]));
				}
			}
		}
		return dist;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		T = kb.nextInt();
		ArrayList<Integer> answer = new ArrayList<>();
		
		for(int t=0; t<T; t++) {//테스트케이스별 실행 
			N= kb.nextInt();
			M = kb.nextInt();
			
			graph = new ArrayList<>();
			for(int i=0; i<=N; i++) {
				graph.add(new ArrayList<>());
			}
			
			//데이터 입력
			for(int i=0; i<M; i++) {
				int a = kb.nextInt();
				int b = kb.nextInt();
				int s = kb.nextInt();
				//양방향 
				graph.get(a).add(new Edge(b, s));
				graph.get(b).add(new Edge(a, s));
			}
			//K가 고정이 아닌데 도대체 어떻게 ? 하지 ???? 
			
			int K =kb.nextInt();//친구 명수 
			//2차원 배열을 만들자/
			int[][] result = new int[K][N+1];//각 시작점 k에 대한 배열 되도록
			
			for(int i=0; i<K; i++) {
				//각각의 친구가 시작값이 되어야 하는데.
				int st = kb.nextInt();
				//임시 배열 
				int[] dist = dijkstra(st);
				
				for(int j=1; j<= N; j++) {//결과를 각 i행에 대한 j열의 배열로 담기 
					result[i][j] = dist[j];//연달아 담아두고.
				}
			}
			int min = Integer.MAX_VALUE;//최대값으로 세팅해두고 
			//답 세팅해야 하잖아
			
			for(int i=1; i<=N; i++) { //각각의 열에 대한 
				int sum = 0;//각 행별 합
				for(int k=0; k<K; k++) {//행 끼리 합
					sum += result[k][i]; //행끼리 누적 
				}
				min = Math.min(min, sum);//가장 작은 합을가진 애가 min 값이다. 
			}
		
			//최종은 가장 작은 값을 가진 애 인덱스 나타나자 마자 세팅하는거임
			for(int i=1; i<=N; i++) {
				int sum = 0;
				for(int k=0; k<K; k++) {
					sum += result[k][i];
				}
				if(sum == min) { //sum 이 min되는 최초의 경우에 
					answer.add(i);//그 정점을 담고 
					break;
				}
			}
		}
		//정답 출력
		for(int x : answer) {
			System.out.println(x);
		}
	}
}

맞아따