[백준] 2479 경로 찾기 [JAVA]

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

2479번: 경로 찾기

이진 수 코드 간 해밍 거리가 1인 이진 수 끼리는 연결돼 있다고 표현한다.

시작 점에서 연결된 이진 수 코드는 거리가 1이고, 연결된 이진 수 코드에서 다시 연결된 이진 수 코드간 거리는 1이므로, 이를 X번 반복해서 목적지 이진 수 코드를 찾을 수 있으면 해밍 거리가 X인 것이다.

이것은 BFS다. 

import java.io.*;
import java.util.*;
public class Main {
	public static int N,K;
	public static boolean visited[];
	public static String str[];
	public static int prev[];
	public static ArrayList<Integer> adj[];
	
	public static int getHamingDist(String a, String b){
		int ans = 0;
		for(int i=0;i<K;i++){
			if(a.charAt(i)!= b.charAt(i)){
				ans++;
			}
		}
		return ans;
	}
	
	public static void getPath(int dest){
		Stack<Integer> q = new Stack<Integer>();
		while(dest!=0){
			q.add(dest);
			dest = prev[dest];
		}
		while(!q.isEmpty()){
			System.out.print(q.pop() + " ");
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		str = new String[N+1];
		visited = new boolean[N+1];
		adj = new ArrayList[N+1];
		prev = new int[N+1];
		for(int i=1;i<=N;i++){
			str[i] = br.readLine();
			adj[i] = new ArrayList<Integer>();
		}
		for(int i=1;i<N;i++){
			for(int j=i+1;j<=N;j++){
				int hamingDist = getHamingDist(str[i],str[j]);
				if(hamingDist == 1){
					adj[i].add(j);
					adj[j].add(i);
				}
			}
		}
		st = new StringTokenizer(br.readLine());
		int start,end;
		start = Integer.parseInt(st.nextToken());
		end = Integer.parseInt(st.nextToken());
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		visited[start] = true;
		while(!q.isEmpty()){
			int curNum = q.poll();
			if(curNum == end){
				getPath(end);
				System.exit(0);
			}
			for(int i=0;i<adj[curNum].size();i++){
				int next = adj[curNum].get(i);
				if(visited[next])continue;
				visited[next] = true;
				q.add(next);
				prev[next] = curNum;
			}
		}
		System.out.println(-1);
	}

}