[Baekjoon] 9694_무엇을 아느냐가 아니라 누구를 아느냐가 문제다

Gold III

문제(출처: https://www.acmicpc.net/problem/9694)

---

< 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 >

 

문제 풀이 

 

데이크스트라를 사용해서 문제를 해결했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _9694_ { // 무엇을 아느냐가 아니라 누구를 아느냐가 문제다
	static class Node implements Comparable<Node> {
		private int node;
		private int d;
		private ArrayList<Integer> list;

		public Node(int node, int d, ArrayList<Integer> list) {
			this.node = node;
			this.d = d;
			this.list = list;
		}

		@Override
		public int compareTo(Node o) {
			return this.d - o.d;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		ArrayList<ArrayList<int[]>> list = new ArrayList<>();
		Node answer[];

		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(bf.readLine());

			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			answer = new Node[m];
			for (int j = 0; j < m; j++) {
				list.add(new ArrayList<>());
				ArrayList<Integer> temp = new ArrayList<>();
				temp.add(j);
				answer[j] = new Node(j, Integer.MAX_VALUE, temp);
			}

			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(bf.readLine());

				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int z = Integer.parseInt(st.nextToken());

				list.get(x).add(new int[] { y, z });
				list.get(y).add(new int[] { x, z });
			}

			PriorityQueue<Node> queue = new PriorityQueue<>();
			ArrayList<Integer> temp = new ArrayList<>();
			temp.add(0);
			answer[0].d = 0;
			queue.add(new Node(0, 0, temp));

			while (!queue.isEmpty()) {
				Node node = queue.poll();

				if (answer[node.node].d < node.d) {
					continue;
				}
				for (int j = 0; j < list.get(node.node).size(); j++) {
					int info[] = list.get(node.node).get(j);
					if (answer[info[0]].d > node.d + info[1]) {
						answer[info[0]].d = node.d + info[1];
						answer[info[0]].list.clear();
						ArrayList<Integer> route = new ArrayList<>();
						for (int k = 0; k < node.list.size(); k++) {
							answer[info[0]].list.add(node.list.get(k));
							route.add(node.list.get(k));
						}
						answer[info[0]].list.add(info[0]);
						route.add(info[0]);
						queue.add(new Node(info[0], node.d + info[1], route));
					}
				}
			}

			bw.write("Case #" + (i + 1) + ": ");

			if (answer[m - 1].d == Integer.MAX_VALUE) {
				bw.write("-1\n");
			} else {
				for (int j = 0; j < answer[m - 1].list.size(); j++) {
					bw.write(answer[m - 1].list.get(j) + " ");
				}
				bw.write("\n");
			}
			list.clear();
		}
		bw.flush();
	}
}

변수)
Node : 번호, 친밀도, 만난 순서
t : 테스트케이스 수
list : 정치인들 간의 친밀도 관계
answer : 0번에서 각 정치인까지 친밀도
n, m : 관계의 개수, 정치인의 수
x, y, z : 정치인 x, 그의 친구 y, 두 사람 간의 친밀도
queue : Node를 가진 우선순위 큐 (친밀도가 낮은 것을 우선순위로 가짐)

 

Node

정치인의 번호, 친밀도, 만난 순서를 변수로 가짐. 우선순위는 친밀도가 낮은 것을 우선으로 함

 

Main

테스트케이스 수만큼 0번에서 m-1번까지 낮은 친밀도를 가질 수 있는 만난 순서를 구한다.

정치인들 간의 관계를 입력받아 list에 양방향으로 저장한다. 

우선순위 큐에 0번을 넣어 친밀도를 구한다. 우선순위 큐가 빌 때까지 반복한다. 우선순위 큐에서 값을 꺼내 자신과 연결된 다른 정치인들을 살펴보며 친밀도의 합이 현재 저장된 친밀도보다 작은 값이라면 값을 업데이트하며 우선순위 큐에 저장한다.

 

answer의 m-1번째 친밀도 값이 Integer.MAX_VALUE라면 최고 의원을 만날 수 없다는 뜻이므로 -1을 출력하고 Integer.MAX_VALUE가 아니라면 answer의 m-1번째에 저장된 list의 값을 출력한다.

---

---