경로 찾기

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

제한시간: 1 초

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

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

프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력

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

출력

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

만약 답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1 을 출력한다.

입출력 예

출처:koi 초등지역기출
special judge:Fate

hammming code 란?

hammming code 는 오류 탐지(error detection) 뿐만 아니라 hamming distance 를 이용하여 오류 수정(error correction)까지 가능한 code 이다.

hamming distance 는 두 코드를 이진수 형태로 나타내었을 때 서로 다른 비트 수이다.

예를 들어 , 16 진수 554 와 234의 hamming distance 는 5 이다.

        0x554 = 0101 0101 0100
        0x234 = 0010 0011 0100
bit difference   xxx  xx       ............. x 는 다름을 의미

만약 사용하는 코드들의 hamming distance 가 3 인 경우 어떤 코드가 중간에 오류가 발생하여 한 비트가 바뀐 경우 수신 한 측에서는 모든 코드들의 bit difference 를 계산하여 0 혹은 1 인 코드를 맞는 코드로 인식한다. 즉 hamming distance 가 3 인 경우 1 비트 오류까지는 탐지와 수정이 가능하다.

코드의 비트수가 늘어나는 단점이 있다.

[질/답] [제출 현황] [푼 후(4)]

[ 채 점 ] [홈으로] [뒤 로]