[백준] 25430번 : 다이제스타

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

25430번: 다이제스타

해당 문제는 조건이 여러가지가 있습니다.

1. 양방향 연결통로

2. 이동방법 중 총 이동 거리가 가장 짧은 경로를 이용한다.

3. 항상 전에 이동했던 연결통로보다 더 길이가 긴 연결통로를 이용해야만 한다. 

4. 한번도 연결통로를 이용한 적이 없다면, 아무 연결통로나 이용 할 수 있다.

 

Node 클래스를 만들어 현재 위치, 총 소요 거리, 이전 거리를 저장한다.

dist도 1차원이 아닌 2차원을 활용하는데, 노드는 int 이동 거리는 long이므로 기본적인 배열을 활용할 수는 없다.

그렇다면 어떻게 활용해야할까?

 

ArrayList<Node> arr를 활용할까?

 - 노드 값에 따른 cost 값에 따른 prev를 바꿀 수 있을까?

 - 같은 값이 들어오면 바꾸는게 가능할까?

No. 할 수 없다고 판단했습니다.

 

그렇다면 "Map이 put을 할때마다 이미 있는 값이 있을 경우 value값을 수정해준다"라는 시스템을 활용하고자 했습니다.

단 node는 어차피 int형이니 Map 배열을 활용하면 어떨까? 라고 생각했습니다.

Map<Long, Long>[] map;

 - 노드 값에 따른 cost에 따른 prev를 바꿀 수 있을까? 

  - Yes, 배열의 크기를 node 처음 키 값을 cost로 하면 value에 들어갈 prev를 바꿀 수 있습니다.

 - 같은 값이 들어오면 바꾸는게 가능할까?

  - map은 키 값에 따라 중복을 제거해 value 값을 수정하므로 충분히 가능합니다.

 

이러한 내용을 활용해 본다면 충분히 풀이가 가능합니다.

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

public class Main {
	static int n;
	static ArrayList<Node>[] arr;
	static HashMap<Long, Long>[] map;
	public static void main(String[] args) throws NumberFormatException,IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		map = new HashMap[n + 1];
		arr = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++) {
			map[i] = new HashMap<>();
			arr[i] = new ArrayList<>();
		}
		
		while(m --> 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			long cost = Integer.parseInt(st.nextToken());
			
			arr[a].add(new Node(b, cost, 0));
			arr[b].add(new Node(a, cost, 0));
			
			map[a].put(cost, Long.MAX_VALUE);
			map[b].put(cost, Long.MAX_VALUE);
		}
		
		st = new StringTokenizer(br.readLine());
		
		long result = dijkstra(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		
		System.out.print(result == Long.MAX_VALUE ? "DIGESTA" : result);
	}
	
	public static long dijkstra(int start, int end) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		
		pq.add(new Node(start, 0, 0));
		map[start].put((long)0, (long)0);
		
		long answer = Long.MAX_VALUE;
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			
			if(now.cost > map[now.to].get(now.prev)) {
				continue;
			}
			
			if(now.to == end) {
				answer = Math.min(answer, now.cost);
			}
			
			for(Node a : arr[now.to]) {
				if(map[a.to].get(a.cost) > now.cost + a.cost && now.prev < a.cost) {
					map[a.to].put(a.cost, now.cost + a.cost);
					pq.add(new Node(a.to, map[a.to].get(a.cost), a.cost));
				}
			}
		}
		return answer;
	}
}

class Node implements Comparable<Node>{
	int to;
	long cost, prev;
	
	public Node(int to, long cost, long prev) {
		this.to = to;
		this.cost = cost;
		this.prev = prev;
	}
	
	@Override
	public int compareTo(Node o) {
		return (int)(this.cost - o.cost);
	}
}