[백준 2479] 경로 찾기 (Java)

문제 링크: www.acmicpc.net/problem/2479

2479번: 경로 찾기

1. 주의할 점

- 다익스트라 알고리즘 + 경로 찾기 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 코드를 li 리스트에 담는다

- calHamilton() 함수를 통해 각 코드 사이의 해밀턴 거리를 Arr[][]에 저장한다

- Dijkstra() 함수를 통해 시작점부터 목표지점까지의 최단거리를 구한다. 이때, 두 코드간의 최단거리가 갱신된다면 Pre[]함수를 통해 이전 경로를 저장한다. 만약 최단거리를 구한 경우, Finish를 True로 변환하여 최단거리가 있다는 표시를 한다.

- Finish가 false인 경우에 -1을 출력하고 아닌 경우에는 Pre[] 배열을 통해 최단거리 경로를 역추적하면서 방문했던 코드번호를 Stack에 담고, 모두 담은 경우 차례대로 출력한다

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

public class Main {  
    static List<String> li;
    static int dist[],pre[];
    static int arr[][];
    static int num,len,from,to;
    static boolean finish;
    
    static void calHamilton(){
        for(int i=0;i<num-1;i++){
            for(int j=i+1;j<num;j++){
                int diff=0;
                for(int k=0;k<len;k++)
                    if(li.get(i).charAt(k)!=li.get(j).charAt(k))
                        diff++;
                arr[i+1][j+1]=diff;
                arr[j+1][i+1]=diff;
            }
        }
    }
    
    static void dijkstra(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(from);
        dist[from]=0;
        pre[from]=from;
        while(!q.isEmpty()){
            int cidx = q.poll();
            if(cidx==to){
                finish=true;
                break;
            }
            for(int i=1;i<=num;i++){
                if(cidx==i) continue;
                if(dist[i]>dist[cidx]+1 && arr[i][cidx]==1){
                    dist[i]=dist[cidx]+1;
                    q.offer(i);
                    pre[i]=cidx;
                }
            }
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String ss = br.readLine();
        StringTokenizer st = new StringTokenizer(ss);
        num = Integer.parseInt(st.nextToken());
    	len = Integer.parseInt(st.nextToken());
    	
    	//초기화
    	finish=false;
    	dist = new int[num+1];
    	Arrays.fill(dist,Integer.MAX_VALUE);
    	pre = new int[num+1];
    	arr = new int[num+1][num+1];
    	li = new ArrayList<>();
    	for(int i=0;i<num;i++){
    	    ss = br.readLine().trim();
    	    li.add(ss);
    	}
    	
    	ss = br.readLine();
    	st = new StringTokenizer(ss);
    	from = Integer.parseInt(st.nextToken());
    	to = Integer.parseInt(st.nextToken());
    	
    	calHamilton();
    	dijkstra();
    	if(!finish) System.out.print(-1);
    	else{
    	    Stack<Integer> s = new Stack<>();
    	    int idx = to;
    	    while(true){
    	        s.add(idx);
    	        if(pre[idx]==idx) break;
    	        idx = pre[idx];
    	    }
    	    while(!s.isEmpty()){
    	        System.out.print(s.peek()+" ");
    	        s.pop();
    	    }
    	}
	}
}