백준 | 17396번. 백도어 - 다익스트라 문풀

⬛ 백준 17396번. 백도어 - 다익스트라 문풀

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

17396번: 백도어

문제

유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다.

최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다. 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다. 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다. 그러나 유섭이의 챔피언이 모든 분기점을 지나칠 수 있는 것은 아니다. 백도어의 핵심은 안 들키고 살금살금 가는 것이기 때문에 적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다.

입력으로 각 분기점을 지나칠 수 있는지에 대한 여부와 각 분기점에서 다른 분기점으로 가는데 걸리는 시간이 주어졌을 때, 유섭이가 현재 위치에서 넥서스까지 갈 수 있는 최소 시간을 구하여라.

입력

첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다. ai가 0이면 i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a0 = 0, aN-1 = 1이다., N-1번째 분기점은 상대 넥서스이기 때문에 어쩔 수 없이 상대의 시야에 보이게 되며, 또 유일하게 상대 시야에 보이면서 갈 수 있는 곳이다.

다음 M개의 줄에 걸쳐 세 정수 a, b, t가 공백으로 구분되어 주어진다. (0 ≤ a, b < N, a ≠ b, 1 ≤ t ≤ 100,000) 이는 a번째 분기점과 b번째 분기점 사이를 지나는데 t만큼의 시간이 걸리는 것을 의미한다. 연결은 양방향이며, 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개 존재한다.

출력

첫 번째 줄에 유섭이의 챔피언이 상대 넥서스까지 안 들키고 가는데 걸리는 최소 시간을 출력한다. 만약 상대 넥서스까지 갈 수 없으면 -1을 출력한다.

💚나의 풀이

• 처음 제출했을 때 틀렸다고 나와서 다시 보았는데, N, M, t 입력 최대가 모두 10만 이상씩이다.
• 따라서 거리 배열 distance는 int형이 아닌 long 타입이어야 한다.
• long 타입으로 바뀌면서 Edge 가중치 변수도 long 타입으로 바꾸고, Long.MAX_VALUE로 초기화값도 바꿔야 정답이 맞다.
• 그리고 들키면 안되는 값이 1인 지점의 정점은 처음부터 방문 true 처리를 해서 아예 방문도 막아버렸다.
• 그 외에는 다익스트라의 일반적인 풀이와 같다.

package to_0831_5;

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

/*17396번. 백도어 - 다익스트라 문풀 */
class Edge implements Comparable<Edge>{
	int e;
	long val;
	Edge(int e, long distance){
		this.e = e;
		this.val = distance;
	}
	@Override
	public int compareTo(Edge o) {
		 if(this.val - o.val > 0) return 1;
         else return -1; 
	}
}
public class Main {
	static int N, M;
	static boolean[] visited;
	static int[] view;
	//경로저장용 배열을 int가 아닌 long으로 해줘야 정답이 맞다. 
	//이유 : N이 10만 M이 30만이다. 둘을 곱하면 이미 10억이 넘는다. 
	// N이 최대 100000, t이 최대 100000 이기 때문에 N * t = 10000000000 이므로 int 범위를 벗어난다. long으로 ㄱㄱ	 
	static long[] distance;
	static ArrayList<ArrayList<Edge>> graph;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		
		view = new int[N];
		visited =new boolean[N];
		distance = new long[N];
		// distance가 long타입이니까 fill로 채울 떄도 Long타입으로 채울 것 
		Arrays.fill(distance, Long.MAX_VALUE);
		
		graph = new ArrayList<>();
		for(int i=0; i<N; i++) {
			graph.add(new ArrayList<>());
		}
		
		//데이터 입력 - view 
		for(int i=0; i<N; i++) {
			view[i] = kb.nextInt();
		}
		//마지막 말고 그 전의 1인 값에 대해서는 visited 방묺앴따고 처리할 거 
		for(int i=0; i<N-1; i++) {
			if(view[i] == 1) {
				visited[i] = true;//방문 처리 
			}
		}
		
		//데이터 입력 - 그래프
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			long v = kb.nextInt();
			//양방향 
			graph.get(a).add(new Edge(b, v));
			graph.get(b).add(new Edge(a, v));
		}
		//다익스트라 시작 
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		distance[0]=0;
		pQ.offer(new Edge(0, 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( distance[nx.e] > distance[cur.e] + nx.val) {
					distance[nx.e] = distance[cur.e] + nx.val;
					pQ.offer(new Edge(nx.e, distance[nx.e]));
				}
			}
		}
		//정답 출력 
		if(distance[N-1] == Long.MAX_VALUE) { //long 타입 
			//방문이 안됐다는 거니까 
			System.out.println("-1");
		}else {
			System.out.println(distance[N-1]);
		}	
	}
}