[더블릿 - 8] 해밍 경로/koi_path

프로그램 명: koi_path(open,special judge)

제한시간: 2 초

길이가 같은 두 개의 이진수 코드 과 가 있다고 하자.

이 두 코드 사이의 해밍 거리(Hamming distance)는 의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다.

예를 들어, , 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 해밍 거리는 2이다

KOI 연구소는 특정 암호문에서 사용되는 총 N개의 이진 코드를 가지고 있다. 각 코드의 길이는 K로 일정하다. 연구소는 이 코드들에 대해 여러 가지 특징을 분석하고 있다.

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

두 코드 와  사이의 해밍 거리를 로 표현한다.

그러면, hd(w1,w2) = 3, hd(w1,w3) = 1, hd(w1,w4) = 2, hd(w1,w5) = 1

당신은 이진 코드들에 대해 해밍 경로를 찾고자 한다. 해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서  는 길이가 3인 해밍 경로이지만, 는 해밍 경로가 아니다. 두 코드 사이에 해밍 경로가 여러 개가 있을 경우 가장 짧은 경로를 찾고자 한다

이 문제는 1번 코드에서부터 질의로 주어진 여러 개의 코드까지의 해밍 경로를 각각 구하는 프로그램을 작성하는 것이다. 프로그램의 실행시간은 2초를 넘을 수 없다.

입력

• 첫째 줄에는 두 개의 정수 N(3≤N≤100,000)과 K(2≤K≤30)가 빈칸을 사이에 두고 주어진다.

• 둘째 줄부터 N개의 줄에는 각 줄마다 길이가 K인 이진 코드가 하나씩 주어진다.
  하나의 코드는 빈칸이 없이 주어지며, 코드들은 주어진 순서대로 1부터 N까지의 번호로 구분된다. 코드가 같은 경우는 없다.

• 그 다음 줄에는 해밍 경로를 찾고자하는 질의의 수인 하나의 정수 M(2≤M≤50)이 주어진다.

• 그 다음 M개의 줄에는 각 줄마다 한 개의 양의 정수 J(2≤J≤N)가 주어진다. J는 1번 코드와 J번 코드 사이의 해밍 경로를 구하라는 질의에 해당한다. J는 모두 다르다.

출력

출력은 M개의 줄로 구성된다.각 줄에는 입력으로 주어진 각 질의에 대한 답을 순서대로 출력한다.

만일 두 코드 사이에 해밍 경로가 존재하면 가장 짧은 경로에 있는 코드들의 번호를 1번 코드부터 차레로 하나의 빈칸을 사이에 두고 출력한다. 답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1을 출력한다.

입출력 예

입력

5 3
000
111
010
110
001
2
4
2

출력

1 3 4
1 3 4 2

출처 : KOI 2010 지역본선 3번
special judge: Fate
참고 : http://211.228.163.31/pool/hamming_distance/hamming_distance.php?pname=hamming_distance 

이 문제는 이전 문제와 이어지는 문제다.

[더블릿 - 7] 경로 구하기/hamming_distance

그래서 쉽게 통과할 수 있을지 알았으나.. 시간초과의 벽에 가로막혀 계속 실패를 하였다.

stl의 vector, queue, stack을 사용하다가 이거때문에 느린건가 생각하여

전부 다 직접 구현해서 제출해봤지만, 조금 빨리질뿐 여전히 시간 초과였다.

인터넷에서 이 문제를 푼 사람들의 코드를 보니 처음 내가 사용했던 알고리즘 자체가 문제였음을 알게되었다.

BFS를 사용하기위해 큐에 데이터를 집어넣을때가 문제였는데

처음엔 한 코드에 대해서 나머지 코드들과 해밍경로가 되는지를 비교해보면서

큐에 데이터들을 넣었다.

이렇게 하면 총 반복 횟수는 n^2 번이 된다.

하지만, 이걸 다르게 생각하여

어느 한 코드에 대해서 해밍경로를 만족하는 것들이

입력받은 데이터에 있는지를 비교해보는것으로 바꾸면

반복 횟수는 k*n번이된다.

n은 최대 100000, k는 최대 30임을 감안하면

엄청 많이 단축됨을 알 수 있다.

즉, 이 문제의 핵심 포인트는

첫 째, BFS를 사용하는가? 이고

두 번째, 해밍 경로를 어떻게 찾을것인가? 이다.

#include <iostream>

#include <utility>

#include <algorithm>

using namespace std;

 

const int nMax = 100000;

const int kMax = 30;

char inputCode[kMax + 1];

typedef pair<int, int> pType;

pType arrInputCode[nMax];

pType arrInputCopy[nMax];

int arrPreviousCode[nMax];

int qBFS[nMax];

int qCount;

int sBFS[nMax];

int sCount;

int n, k;

int arrBin[kMax];

 

int str2i(char *cStr)

{

    int i, res = 0;

    for(i = 0; i < k; ++i){

        if (cStr[i] == '1')

            res += arrBin[i];

    }

    return res;

}

 

int bsearch(int k)

{

    int low = 0, high = n - 1, mid;

    int c = 0;

    for(;;)

    {

        mid = (low + high)/2;

        if (arrInputCopy[mid].second == k)

            return arrInputCopy[mid].first;

        if (arrInputCopy[mid].second > k)

            high = mid - 1;

        else

            low = mid + 1;

        if (low > high)

            return -1;

    }

}

 

void BFSSet()

{

    int t;

    int pCode;

    int qStart = 0, qTotalCount = 0;

    qBFS[qTotalCount++] = arrInputCode[0].first;

    arrPreviousCode[0] = -1;

    ++qCount;

 

    while (qCount)

    {

        pCode = qBFS[qStart++];

        --qCount;

 

        for (int i = 0; i < k; ++i)

        {

            t = bsearch(arrInputCode[pCode - 1].second ^ arrBin[i]);

            if (t == -1)

                continue;

            if (arrPreviousCode[t - 1] == 0)

            {

                arrPreviousCode[t - 1] = pCode;

                qBFS[qTotalCount++] = t ;

                ++qCount;

            }

        }

    }

}

 

void BFSPrint(int B)

{

    sCount = 0;

    if (arrPreviousCode[B - 1] == 0)

        cout << -1;

    else

    {

        sBFS[sCount++] = arrInputCode[B - 1].first;

 

        while ((sBFS[sCount] = arrPreviousCode[sBFS[sCount - 1] - 1])!=-1)

            sCount++;

 

        while(sCount--)

            cout << sBFS[sCount] << " ";

    }

    cout << endl;

}

 

bool cmp(pType l, pType r)

{

    return l.second < r.second;

}

 

int main()

{

    cin >> n >> k;

 

    for (int i = 0; i < k; ++i)

        arrBin[i] = 1 << i;

 

    for (int i = 0; i < n; ++i)

    {

        cin >> inputCode;

        arrInputCopy[i].first = arrInputCode[i].first = i + 1;

        arrInputCopy[i].second = arrInputCode[i].second = str2i(inputCode);

    }

    sort(arrInputCopy + 0,arrInputCopy + n, cmp);

 

    BFSSet();

 

    int m, mB;

    cin >> m;

    for (int i = 0; i < m; ++i)

    {

        cin >> mB;

        BFSPrint(mB);

    }

    return 0;