[BOJ] 9370. 미확인 도착지 - JAVA

🔗 문제

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

9370번: 미확인 도착지

 

🧩 풀이 및 코드

문제 유형 : 그래프 이론, 다익스트라

 

풀이

문제는 시작정점에서 목적지 정점까지 가는 최단 경로 중 g-h 또는 h-g 를 포함하는 목적지를 찾는 것이다.

g-h 를 뺀 나머지 간선들의 비용은 짝수로, g-h 는 홀수로 변경해서 만약, 최단경로가 홀수라면 g-h 를 포함한 경로이므로 목적지 후보에 포함시킨다.

 

느낀 점

이걸 어떻게 생각하지...

 

 

전체 코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

/*
 * 목적지 후보 중에서 s-g 또는 g-s 를 거치는 최단경로를 가진 목적지만 출력하기
 * sol)
 * s-g 가중치만 홀수로 바꿔서 최단경로 비용이 홀수라면 이 가중치를 포함한 경로
 */

public class Main_bj_9370_미확인도착지 {
	
	static int INF = 100_000_000;
	
	static class Node {
		int to;
		int weight;
		Node link;
		
		Node(int to, int weight, Node link) {
			this.to = to;
			this.weight = weight;
			this.link = link;
		}
	}

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_9370.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st;
		int n, m, t, s, g, h, u, v, w;
		Node[] adjList;
		int[] distance;
		List<Integer> candidate;
		boolean[] visited;
		for(int tc=0; tc<T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			n = Integer.parseInt(st.nextToken());		// 정점의 갯수
			m = Integer.parseInt(st.nextToken());		// 간선의 갯수
			t = Integer.parseInt(st.nextToken());		// 목적지 후보의 갯수
			
			st = new StringTokenizer(br.readLine(), " ");
			s = Integer.parseInt(st.nextToken());		// 출발지
			g = Integer.parseInt(st.nextToken());		// 듀오가 지나간 정점 u
			h = Integer.parseInt(st.nextToken());		// 듀유가 지나간 정점 v
			
			adjList = new Node[n+1];
			// 양방향 도로
			for(int i=0; i<m; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				u = Integer.parseInt(st.nextToken());
				v = Integer.parseInt(st.nextToken());
				w = Integer.parseInt(st.nextToken());
				
				if((u==g && v==h) || (u==h && v==g)) {
					w = w*2-1;			// 홀수로 변경
				} else {
					w *=2;				// 짝수로 변경
				}
				
				adjList[u] = new Node(v, w, adjList[u]);
				adjList[v] = new Node(u, w, adjList[v]);
			}
			
			// 목적지 후보 저장
			candidate = new ArrayList<>();
			for(int i=0; i<t; i++) {
				candidate.add(Integer.parseInt(br.readLine()));
			}
			Collections.sort(candidate);
			
			// dijkstra
			distance = new int[n+1];
			Arrays.fill(distance, INF);
			distance[s] = 0;
			
			PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));		// 최소 우선순위 큐
			pq.add(new int[] {s, 0});
			
			visited = new boolean[n+1];
			
			while(!pq.isEmpty()) {
				int[] now = pq.poll();
				
				if(visited[now[0]]) continue;
				visited[now[0]] = true;
				
				// 이웃 검사
				for(Node temp = adjList[now[0]]; temp!=null; temp=temp.link) {
					if(!visited[temp.to] && distance[temp.to] > now[1] + temp.weight) {
						distance[temp.to] = now[1] + temp.weight;
						pq.add(new int[] {temp.to, distance[temp.to]});
					}
				}
			}
			
			for(int d : candidate) {
				if(distance[d]%2 == 1) {		// g-h 를 거친 최단경로
					sb.append(d).append(" ");
				}
			}
			sb.append("\n"); 
		}
		
		System.out.println(sb.toString());
		br.close();
	}

}

 

---

Reference

https://pangtrue.tistory.com/255

[백준 9370 : JAVA] 미확인 도착지 / 다익스트라