[C/C++] 백준 - 2479번 : 경로 찾기

https://www.acmicpc.net/problem/2479

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을 출력한다.

---

문제에 주어진 조건에 맞게 시작 코드부터 끝 코드까지의 최단 경로를 구해야한다. 이러한 문제 형식은 BFS 알고리즘으로 해결할 수 있다.

조건과 일치하는 코드는 모두 큐에 담아놓고 하나씩 꺼내 목표 코드와 일치하는지 확인하는 방식으로 진행한다.

 

BFS 알고리즘을 진행하는 것은 어렵지 않으나, 최단경로를 출력하는 부분을 어떻게 해야할지 고민이 필요하다.

 

최단 경로를 출력하는 방법은 하나의 배열을 선언하여 현재의 코드 인덱스 번호로 오기 전 코드의 인덱스를 담는 것이다.

 

문제의 예제로 예를 들어보자면, 최단 경로는 1 → 3 → 4 → 2이다.

 

위 경로를 역순으로 저장한다고 생각하면 된다.

 

[2]라는 인덱스 코드로 해밍경로를 진행하기 위해서는 [4]인덱스에서 진행해야한다. 따라서, 경로를 저장하는 배열 인덱스 2에 4를 담아준다. 똑같이 [4]라는 인덱스 코드로 해밍경로를 진행하기 위해서는 [3] 인덱스에서 진행해야한다. 똑같이 경로저장 배열 인덱스 4에는 3을 담아준다. 

 

목표 지점에 도달했을 때, 지금까지 저장했던 경로 배열을 DFS 알고리즘을 진행하게 되면 진행했던 경로를 역순으로 확인할 수 있다. 

 

이를 다시 역순으로 출력하게 되면 최단 해밍 경로를 출력할 수 있다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 987654321
#define endl '\n'

using namespace std;

vector<string> op;
bool visited[1000 + 1];
int backtracking[1000 + 1];
int N, K, start, purpose;

void input(){
    cin >> N >> K;
    op.resize(N+1);
    for(int i=1;i<=N;i++){
        cin >> op[i];
    }

    cin >> start >> purpose;
    backtracking[start] = -1;
}

bool isValid(string str, int index){
    int count = 0;
    for(int i=0;i<str.size();i++){
        if(str[i] == op[index][i]) continue;
        count++;
        if(count > 1) return false;
    }
    if(count == 1) return true;
    return false;
}

void dfs(int index, vector<int> &ps){
    ps.push_back(index);
    if(backtracking[index] == -1) return;

    dfs(backtracking[index], ps);
}

void solution(){
    vector<int> ps;
    queue<pair<int, string>> q;

    visited[start] = true;
    q.push({start, op[start]});

    while(!q.empty()){
        pair<int, string> cur = q.front();
        q.pop();

        if(cur.first == purpose) {
            dfs(cur.first, ps);
            break;
        }

        for(int i=1;i<=N;i++){
            if(visited[i]) continue;
            if(isValid(cur.second, i)){
                backtracking[i] = cur.first;
                visited[i] = true;
                q.push({i, op[i]});
            }
        }
    }
    if(ps.empty()) {
        cout << -1 << endl;
    } else{
        for(int i=ps.size()-1;i>=0;i--){
            cout << ps[i] << " ";
        }
    }
}

int main(){
    fastio;
    input();
    solution();

    return 0;
}