[백준 1240] 노드사이의 거리 (Java)

문제 링크: https://www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

1. 주의할 점

- 초기화 작업을 거친다

- 다익스트라나 플로이드와샬 알고리즘에 대해 알고 있으면 해결할 수 있다(Tree라서 DFS도 간단히 가능)

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

class Main {
    static final int MAX = 987654321;
    static int node,query;
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    node = Integer.parseInt(st.nextToken());
	    query = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    int arr[][] = new int[node+1][node+1];
	    for(int i=1;i<=node;i++)
	        for(int j=1;j<=node;j++){
	            arr[i][j]=MAX;
	            if(i==j) arr[i][j]=0;
	        }
	    
	    for(int i=0;i<node-1;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        int from = Integer.parseInt(st.nextToken());
	        int to = Integer.parseInt(st.nextToken());
	        int val = Integer.parseInt(st.nextToken());
	        arr[from][to]=val;
	        arr[to][from]=val;
	    }
	    
	    for(int k=1;k<=node;k++)
	        for(int i=1;i<=node;i++)
	            for(int j=1;j<=node;j++)
	                if(arr[i][j]>arr[i][k]+arr[k][j])
	                    arr[i][j]=arr[i][k]+arr[k][j];
	    
	    for(int i=0;i<query;i++){
	        str = br.readLine();
    	    st = new StringTokenizer(str);
    	    int a = Integer.parseInt(st.nextToken());
    	    int b = Integer.parseInt(st.nextToken());
	        System.out.println(arr[a][b]);
	    }
	}
}

 

2. 구현

[다익스트라]

- 모든 간선에 대한 정보를 Li[] 배열에 담는다

- A와 B 사이의 최단거리를 구하기 위해 우선순위큐를 사용하는 다익스트라 알고리즘을 수행한다

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

class Main {    
    static final int MAX = 987654321;
    static List<Info> li[];
    static int dist[];
    static int node,query;
    
    static class Info implements Comparable<Info> {
        int idx,val;      
        public Info(int idx, int val){
            this.idx = idx;
            this.val = val;
        }     
        @Override
        public int compareTo(Info o){
            return Integer.compare(this.val,o.val);
        }
    };
    
    static int dijkstra(int a, int b){
        dist = new int[node+1];
        for(int i=1;i<=node;i++)
            dist[i]=MAX;
        dist[a]=0;     
        PriorityQueue<Info> pq = new PriorityQueue<>();
        pq.offer(new Info(a,0));
        Info ii;
        
        while(!pq.isEmpty()){
            ii = pq.poll();
            int cidx = ii.idx;
            int cv = ii.val;
            if(cidx==b) break;
            for(int i=0;i<li[cidx].size();i++){
                int next = li[cidx].get(i).idx;
                int nv = li[cidx].get(i).val;
                if(dist[next]>cv+nv){
                    dist[next]=cv+nv;
                    pq.offer(new Info(next,cv+nv));
                }
            }
        }
        return dist[b];
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    node = Integer.parseInt(st.nextToken());
	    query = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    li = new List[node+1];
	    for(int i=1;i<=node;i++)
	        li[i] = new ArrayList<>();
	    for(int i=0;i<node-1;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        int from = Integer.parseInt(st.nextToken());
	        int to = Integer.parseInt(st.nextToken());
	        int val = Integer.parseInt(st.nextToken());
	        li[from].add(new Info(to,val));
	        li[to].add(new Info(from,val));
	    }
	    for(int i=0;i<query;i++){
	        str = br.readLine();
    	    st = new StringTokenizer(str);
    	    int a = Integer.parseInt(st.nextToken());
    	    int b = Integer.parseInt(st.nextToken());
	        System.out.println(dijkstra(a,b));
	    }
	}
}

[플로이드와샬]

- 모든 간선사이의 거리를 나타내는 Arr[][]를 MAX로 초기화한다(i==j인 경우 0)

- 간선에 대한 정보를 바탕으로 Arr[][]를 갱신한다

- 플로이드와샬 알고리즘을 수행한 이후, Arr[A][B]를 출력한다