[백준]#2479 경로 찾기

문제

길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다.

우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다.

예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다.

A=000, B=111, C=010, D=110, E=001

두 코드 A와 B사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다.

우리는 이진 코드들에 대해 해밍 경로를 찾고자 한다. 해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서 (A,C,D)는 코드 A와 C의 해밍 거리가 1이고, 코드 C와 D의 해밍 거리가 1이므로 해밍 경로이다. (A,E,B)는 코드 A와 E의 해밍 거리는 1이지만, 코드 E와 B의 해밍 거리가 2이므로 해밍 경로가 아니다.

이 문제는 주어진 두 코드 사이에 가장 짧은 해밍 경로를 구하는 프로그램을 작성하는 것이다.

입력

첫째 줄에는 두 개의 정수 N과 K가 빈칸을 사이에 두고 주어진다(3≤N≤1,000, 2≤K≤30). 둘째 줄부터 N개의 줄에는 각 줄마다 길이가 K인 이진 코드가 하나씩 주어진다. 하나의 코드는 빈칸이 없이 주어진다. 코드들은 주어진 순서대로 1부터 N까지의 번호로 구분된다. 코드가 같은 경우는 없다. 그 다음 줄에는 해밍 경로를 찾고자 하는 서로 다른 두 개의 코드 A와 B가 각각의 코드번호로 주어진다.

출력

입력으로 주어진 두 코드 사이에 해밍 경로가 존재하면 그 경로 중 가장 짧은 경로를 코드 A부터 코드 B까지 경로상의 코드 번호로 출력한다. 코드 번호를 출력할 경우에는 코드 번호 사이에 하나의 빈칸을 사이에 두고 출력한다. 만약 답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1을 출력한다.

예제 입력 1

5 3
000
111
010
110
001
1 2

예제 출력 1

1 3 4 2

풀이

이 문제는 BFS, Dijkstra 등의 알고리즘으로 풀 수 있는 문제이다. 본인은 BFS 알고리즘에 back tracking을 이용해서 문제를 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[][] graph;
    static int N;
    static ArrayList<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        String[] binary = new String[N+1];
        graph = new int [N+1][N+1];

        for(int i=1; i<=N; i++) {
            binary[i] = br.readLine();
        }

        String[] input = br.readLine().split(" ");
        int start = Integer.parseInt(input[0]);
        int end = Integer.parseInt(input[1]);

        for(int i=1; i<=N; i++) {
            for(int j=i; j<=N; j++) {
                if(i==j)
                    graph[i][j] = 0;

                else {
                    int cnt = 0;

                    for(int k=0; k<M; k++) {
                        if(binary[i].charAt(k)!=binary[j].charAt(k))
                            cnt++;
                    }

                    if(cnt==1) {
                        graph[i][j]=1;
                        graph[j][i]=1;
                    }

                    else {
                        graph[i][j]=0;
                        graph[j][i]=0;
                    }
                }
            }
        }
        bfs(start, end);
    }

    static void bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
        int[] from = new int[N+1];
        int current = 0;
        visited[start] = true;
        from[start] = -1;
        queue.add(start);

        while(!queue.isEmpty()) {
            current = queue.poll();

            if(current==end)
                break;

            for(int i=1; i<=N; i++) {
                if(!visited[i] && graph[current][i]==1) {
                    visited[i] = true;
                    from[i]=current;
                    queue.add(i);
                }
            }
        }
        if(current != end)
            System.out.println(-1);
        else {
            list.add(end);
            int i=0;
            while(true) {
                int index = list.get(i);
                if(index==start)
                    break;
                list.add(from[index]);
                i++;
            }
            for(int j=list.size()-1; j>=0; j--)
                System.out.print(list.get(j)+" ");
        }
    }
}