백준 2479번 경로 찾기 :: 마이구미

이 글은 백준 알고리즘 문제 11403번 "경로 찾기" 를 풀이한다.

정올 출제 문제로써, 풀이 방법은 DFS 를 통해 해결한다.

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

DFS - https://mygumi.tistory.com/102

길이가 같은 두 개의 이진수 코드 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이므로 해밍 경로가 아니다.

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

문제는 이진 코드, 해밍 거리 등 이러한 용어 때문에 어려워보인다.

하지만 문제를 이해하고보면, 단순한 DFS 문제가 된다.

문제는 가장 짧은 해밍 경로를 구해야한다.

해밍 경로는 두 코드 사이의 해밍 거리가 1이면 된다.

두 코드 사이의 해밍 거리는 서로 다른 값을 가진 비트의 수가 된다.

다음 입력 예제를 표현한 그림을 보면 쉽게 이해할 수 있다.

위 입력 예제는 1과 2 사이의 해밍 경로를 구해야한다.

1과 2 코드 사이의 해밍 경로가 의미하는 것은 1 -> 2 를 가기 위해 도달할 수 있는 경로를 찾는 것이다.

1 코드에서 2 코드는 해밍 거리가 3이기 때문에 바로 도달할 수 없다.

도달하는 방법은 다음과 같다.

1 코드는 해밍 거리가 1인 코드(3)를 거치고, 3 코드는 해밍 거리가 1인 코드(4) 를 거친 후, 2 코드에 도달할 수 있다.

각 코드를 정점이라고 생각하고, 해밍 거리를 기반으로 간선을 연결해주면 된다.

그래프로 표현하면 다음과 같다.

문제는 인접행렬을 이해하고 있다면, 쉽게 해결할 수 있는 문제이다.

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2010/2479.java

static boolean[] visited;
static int[][] adj;
static int n, k, a, b;
static boolean flag;
 
private void solve() {
    n = sc.nextInt();
    k = sc.nextInt();
    String[] s = new String[n];
    adj = new int[n + 1][n + 1];
    visited = new boolean[1001];
 
    for (int i = 0; i < n; i++) {
        s[i] = sc.readLine();
    }
 
    a = sc.nextInt();
    b = sc.nextInt();
 
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (checkHamming(s[i - 1], s[j - 1])) {
                adj[i][j] = 1;
                adj[j][i] = 1;
            }
        }
    }
 
    visited[a] = true;
    dfs(a, a + "");
    if (!flag) {
        System.out.println(-1);
    }
}
 
public static void dfs(int v, String s) {
    if (v == b) {
        flag = true;
        System.out.println(s);
        return;
    } else {
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && adj[v][i] == 1) {
                visited[i] = true;
                dfs(i, s + " " + i);
            }
        }
    }
}
 
public static boolean checkHamming(String s1, String s2) {
    int cnt = 0;
    for (int i = 0; i < k; i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            if (++cnt >= 2) {
                return false;
            }
        }
    }
    if (cnt == 0) {
        return false;
    }
    return true;
}