[JAVA] 9370 미확인 도착지

안녕하세요.

 

어제 저는 오랜만에 영화를 봤는데요. 알고리즘 풀이보다 어렵게 느껴지는 영화였습니다. 

 

그래도 영상미는 아름다워서..좋았어요 팝콘도 맛있고

 

오늘의 문제는

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

9370번: 미확인 도착지

 

문제 설명에 재미있는..?상황극까지 설정해 주지만 그냥 요점만 빠르게 말해주는 게 더 좋더라고요.

 

요점만 빠르게라..제 블로그와는 전혀 맞지 않는 느낌이네요.yo

 

그럼 이제라도 바로 문제를 풀어보겠습니다.

 

<나의 풀이> 

 

문제를 요약하자면 출발점(s)에서 출발하여 목적지 후보들 중 특정 경로(g>h)를 지나며, 최단거리가 가능한 목적지 후보를 구해내야 합니다. 

 

게다가 하나의 input에 여러 개의 케이스(T)가 주어집니다. 

 

특정 지점에서 최단거리를 구하는 알고리즘은 다익스트라 알고리즘이 있죠. 단 다익스트라 알고리즘을 사용하기 전 간선의 값들이 양수인지 꼭 확인을 해줘야 합니다.

 

다익스트라 알고리즘의 시간복잡도는 O(n^2)입니다. 하지만 qp를 사용한다면 O(n* logn)정도로 최적화시킬 수 있습니다. 

0 <T <=100 이긴 한데, 시간제한이 3초로 좀 낭낭하게 있으니 큰 걱정은 하지 않았습니다. 

 

저는 이때만 해도, 이미 다 풀고 누워있을 생각을 했었습니다. 하지만 진짜 문제는 이제부터입니다. 

 

앞에서 말한 것처럼, 두 가지의 조건을 만족하는 목적지들을 구해야 합니다. 

 

1. 스위치를 사용하여 표시

 

 boolean 값을 사용하여 특정경로를 지났는지 체크를 하는 방법을 생각했었습니다. boolean 값을 체크할 때, 시작점과 도착점의 boolean 값을 확인해서 하나의 값이라도 true라면 true로 바꿔줬습니다. 

 

하지만 만일 중복되는 최단거리가 존재하고, 하나는 특정 경로를 지나고 다른 하나는 지나지 않는 경우에는 boolean값이 의도한 역할을 수행하지 못했습니다. ㅠ

 

2. 머였지..아 기준점을 3개로 나눠 확인

 

특정 경로를 지나는 최단거리를 구해야 하니까 특정 경로를 시작점으로 생각하여 다익스트라 알고리즘을 사용하였습니다.

 

1) 출발점, dist1[ ]

2) g>h 방향 (즉 g 시작) dist2[ ]

3) h>g 방향 (즉 h시작) dist3[ ]

 

이렇게 해서 3개의 최단거리 배열을 구하고, dist1 [ i ] = dist 2[ i ] + dist1 [g] 와 dist1 [ i ] = dist3 [ i ] + dist1 [h] 인지 확인해서 문제를 풀어보았습니다.

지금 심정처럼 삐뚤삐둘

넵 틀렸습니다. 틀린 이유는 2,3의 기준을 하나의 점이 아닌 하나의 경로를 기준으로 잡았기 때문입니다. 

위와 같은 경우에서 g > h 방향만 생각한다면, g > i까지 최단거리는 b+d+e이고 여기에 s > g의 최단거리인 a+b를 합해주는 건 중복된 경로의 합을 구하게 됩니다.

 

3. 기준 3개로 나누기 ver 2

 

1) 출발점, dist1[ ]

2) g출발(즉 g 시작) dist2[ ]

3) h출벌 (즉 h시작) dist3[ ]

 

세부 조건 또한 변경했습니다.

 

dist1[ i ] = dist2 [ i ] + value of g > h + dist1 [ h ]

이 조건의 뽀인트는 빨간색 부분입니다.

우리가 구하고 싶은 것은 'g>h (혹은 h > g)를 지나며 i에 도착하는 경우가 최단거리인지' 입니다.

따라서 s 에서 g(h)까지의 거리와 g< >h의 값을 더한 후 dist2를 더한다면 특정 경로를 지나며 최단거리인지 확인이 가능합니다.

<코드>

import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
	int start;
	int end;
	int value;
	public Node(int s, int e, int v) {
		this.start = s;
		this.end = e;
		this.value = v;
	}
	@Override
	public int compareTo(Node oj) {
		return this.value - oj.value;
	}
}
public class Num9370_2 {
	static int n,m,t,s,g,h,a,b,d;
	static List<Integer> endPoints;
	static List<List<Node>> map; 
	static int[] vist, vist2, vist3;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		StringBuilder sb = new StringBuilder();
		while(T>0) {
			T--;
			//input
			StringTokenizer st = new StringTokenizer(bf.readLine());
			n = Integer.parseInt(st.nextToken());
			map = new LinkedList<>();
			for(int i=0;i<=n;i++) {
				map.add(new LinkedList<>());
			}
			m = Integer.parseInt(st.nextToken());
			t = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(bf.readLine());
			s = Integer.parseInt(st.nextToken());
			g = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			//memo g>h value
			int targetRoadValue = 0;
			for(int i=0;i<m;i++) {
				st = new StringTokenizer(bf.readLine());
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				d = Integer.parseInt(st.nextToken());
				if(a==g && b==h) {
					targetRoadValue = d;
				}
				if(a==h && b==g) {
					targetRoadValue = d;
				}
				map.get(a).add(new Node(a,b,d));
				map.get(b).add(new Node(b,a,d));
			}
			endPoints = new ArrayList<>();
			for(int i=0;i<t;i++) {
				endPoints.add(Integer.parseInt(bf.readLine()));
			}
			//find minimum
			vist = new int[n+1];
			vist2 = new int[n+1];
			vist3 = new int[n+1];
			Arrays.fill(vist,1000000000);
			Arrays.fill(vist2,1000000000);
			Arrays.fill(vist3,1000000000);
			PriorityQueue<Node> que = new PriorityQueue<>();
			//initialize
			vist[s] =0;
			for(Node now : map.get(s)) {
				que.add(now);
			}
			//BFS(startPoint)
			while(!que.isEmpty()) {
				Node now = que.poll();
				if(vist[now.end] > vist[now.start]+now.value) {
					vist[now.end] = vist[now.start]+now.value;
					for(Node nxt : map.get(now.end)) {
						que.add(nxt);
					}
				}
			}
			
			//BFS2
			for(Node now : map.get(g)) {
				que.add(now);
			}
			vist2[g] = 0;
			while(!que.isEmpty()) {
				Node now = que.poll();
				if(vist2[now.end] > vist2[now.start]+now.value) {
					vist2[now.end] = vist2[now.start]+now.value;
					for(Node nxt : map.get(now.end)) {
						que.add(nxt);
					}
				}
			}
			//BFS3
			for(Node now : map.get(h)) {
				que.add(now);
			}
			vist3[h] = 0;
			while(!que.isEmpty()) {
				Node now = que.poll();
				if(vist3[now.end] > vist3[now.start]+now.value) {
					vist3[now.end] = vist3[now.start]+now.value;
					for(Node nxt : map.get(now.end)) {
						que.add(nxt);
					}
				}
			}
			//findAnsewr
			Collections.sort(endPoints);
			for(int candidate : endPoints) {
				if(vist[candidate] == vist2[candidate]+vist[h]+targetRoadValue) {
					sb.append(candidate +" ");
				}else if(vist[candidate] == vist3[candidate]+vist[g]+targetRoadValue){
					sb.append(candidate +" ");
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

}

 

후기

1. Method를 구현했으면 좀 더 보기 편할 텐데..

2. 짝수와 홀수를 이용하면 기가 막히게 풀 수 있음

 > 특정 경로만 홀수로 만들고 나머지들을 다 짝수로 만들어버리면.. 홀수에 거리 값을 가지는 값은 특정경로를 지난 거임!