[Java]백준 BaekJoon.AC 1504 : 특정한 최단 경로 (다익스트라, ArrayList)

 

 

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

1504번: 특정한 최단 경로

 

 

와 다 풀어놓고 삽만 오지게 펐다...

다익스트라 유형 제대로 기억이 안나서 다시 공부해서 풀었다.

다른 코드들 보니 큰 유형은 비슷하고 길이를 기록하는 배열과 다익스트라 함수 실행 방법만 좀 다른 것 같다.

쉽게 실행될 줄 몰랐는데 운이 좋았다.

 

숨겨둔 코드도 프린트 줄만 제거하면 돌아갈거 같다.

<틀린코드>

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

public class Main {
	
	static int N, E;
	static int V1, V2;
    static final int INF = 200000000;
	static ArrayList<Node>[] arr;
	static int[][] result;
    public static void main(String[] args) throws IOException {
        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	arr = new ArrayList[N+1];
    	result = new int[3][N+1];
    	
    	
    	for(int i=0; i<N+1; i++) {
    		arr[i] = new ArrayList<Node>();
    	}
    	
    	for(int i=0; i<E; i++) {
    		st = new StringTokenizer(br.readLine());
    		
    		int s = Integer.parseInt(st.nextToken());
    		int f = Integer.parseInt(st.nextToken());
    		int l = Integer.parseInt(st.nextToken());
    		
    		arr[s].add(new Node(f, l));
        	arr[f].add(new Node(s, l));//양방향 길

    	}
    	
    	st = new StringTokenizer(br.readLine());
    	V1 = Integer.parseInt(st.nextToken());
    	V2 = Integer.parseInt(st.nextToken());
    	
        if(E==0) {
    		System.out.print(-1);
    		return;
    	}
    	
    	for(int i=0; i<3; i++) {
    		Arrays.fill(result[i], INF);
    	}
    	
    	
//    	for(int i=0; i<3; i++) {
//    		for(int j=0; j<N+1; j++) {
//    			System.out.print(result[i][j]+" ");
//    		}
//    		System.out.println();
//    	}
    	
    	
    	for(int i=0; i<3; i++) {
    		cal(i);
    	}
    	
    	int a = result[0][V1] + result[1][V2] + result[2][N];
    	int b = result[0][V2] + result[2][V1] + result[1][N];
    	
        if(Math.min(a, b)>=INF) {
    		System.out.print(-1);
    		return;
    	}
    	System.out.print(Math.min(a, b));
    	
    	
	}
    
    public static void cal(int s) {
    	PriorityQueue<Node> queue = new PriorityQueue<>();
    	boolean[] visit = new boolean[N+1];
    	int start = 0;
    	
    	switch(s) {
			case 0:
				start = 1;  break;
			case 1:
				start = V1; break;
			case 2:
				start = V2; break;
    	}
    	System.out.println();
    	System.out.println("s가 " + s + "이니까 " + start + "시작!");
    	result[s][start]=0;
    	queue.add(new Node(start, 0));
    	
    	while(!queue.isEmpty()) {
    		Node temp = queue.poll();
    		System.out.println("Queue에서 꺼낸 노드: (" + temp.fin + ", " + temp.len + ")");
    		if(visit[temp.fin]) continue;
    		
    		for(Node a : arr[temp.fin]) {
    			System.out.println("arr 꺼내기! (" + a.fin + ", " + a.len + ")");
    			System.out.println(a.len + "+" + result[s][temp.fin]+"<"+result[s][a.fin]);
    			if(a.len+result[s][temp.fin]<result[s][a.fin]) {
    				System.out.println("통과! Queue에 (" + a.fin+ ", " + a.len + ") 추가!");
    				result[s][a.fin]=a.len+result[s][temp.fin];
    				queue.add(new Node(a.fin, result[s][a.fin]));
    			}
    		}
    		
    		System.out.println();
    		for(int i=0; i<3; i++) {
    			System.out.println();
    			for(int j=1; j<N+1; j++) {
    				System.out.print(result[i][j] + " ");
    			}
    		}
    		System.out.println();
    		System.out.println();
    		
    		visit[temp.fin]=true;
    		
    		
    	}
    	
    	Arrays.fill(visit, false);
    	
    }
}

class Node implements Comparable<Node>{

	int fin;
	int len;
	
	Node(int fin, int len){
		this.fin = fin;
		this.len = len;
	}

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

 

 

 

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

public class Main {
	
	static int N, E;
	static int V1, V2;
	static final int INF = 200000000;
	static ArrayList<Node>[] arr;
	static int[][] result;
    public static void main(String[] args) throws IOException {
        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	arr = new ArrayList[N+1];
    	result = new int[3][N+1];
    	
    	
    	for(int i=0; i<N+1; i++) {
    		arr[i] = new ArrayList<Node>();
    	}
    	
    	for(int i=0; i<E; i++) {
    		st = new StringTokenizer(br.readLine());
    		
    		int s = Integer.parseInt(st.nextToken());
    		int f = Integer.parseInt(st.nextToken());
    		int l = Integer.parseInt(st.nextToken());
    		
    		arr[s].add(new Node(f, l));
        	arr[f].add(new Node(s, l));//양방향 길

    	}
    	
    	st = new StringTokenizer(br.readLine());
    	V1 = Integer.parseInt(st.nextToken());
    	V2 = Integer.parseInt(st.nextToken());
    	
        if(E==0) {
    		System.out.print(-1);
    		return;
    	}
    	
    	for(int i=0; i<3; i++) {
    		Arrays.fill(result[i], INF);
    	}
    	
    	for(int i=0; i<3; i++) {
    		cal(i);
    	}
    	
    	int a = result[0][V1] + result[1][V2] + result[2][N];
    	int b = result[0][V2] + result[2][V1] + result[1][N];
    	
        if(Math.min(a, b)>=INF) {
    		System.out.print(-1);
    		return;
    	}
        
    	System.out.print(Math.min(a, b));
    	
    	
	}
    
    public static void cal(int s) {
    	PriorityQueue<Node> queue = new PriorityQueue<>();
    	boolean[] visit = new boolean[N+1];
    	int start = 0;
    	
    	switch(s) {
			case 0:
				start = 1;  break;
			case 1:
				start = V1; break;
			case 2:
				start = V2; break;
    	}
    	
    	queue.add(new Node(start, 0));
    	result[s][start]=0;
    	
    	while(!queue.isEmpty()) {
    		Node temp = queue.poll();
    		if(visit[temp.fin]) continue;
    		
    		for(Node a : arr[temp.fin]) {
    			if(a.len+result[s][temp.fin]<result[s][a.fin]) {
    				result[s][a.fin]=a.len+result[s][temp.fin];
    				queue.add(new Node(a.fin, result[s][a.fin]));
    			}
    		}   		
    		
    		visit[temp.fin]=true;
    		    		
    	}
    	
    	Arrays.fill(visit, false);
    	
    }
}

class Node implements Comparable<Node>{

	int fin;
	int len;
	
	Node(int fin, int len){
		this.fin = fin;
		this.len = len;
	}

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