해밍 경로 > 문제은행



알고리즘 BFS2

2263 : 해밍 경로

제한시간: 2000 ms    메모리제한: 128 MB
해결횟수: 66 회    시도횟수: 553 회    Special Judge



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

 

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

 

w1=000, w2=111, w3=010, w4=110, w5=001

 

두 코드 wi와 wj 사이의 해밍 거리를 hd(wi,wj)로 표현한다. 그러면, hd(w1,w2) = 3, hd(w1,w3) = 1, hd(w1,w4) = 2, hd(w1,w5) = 1 이다.

 

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

 

이 문제는 1번 코드에서부터 질의로 주어진 여러 개의 코드까지의 해밍 경로를 각각 구하는 프로그램을 작성하는 것이다.


첫째 줄에는 두 개의 정수 N과 K가 빈칸을 사이에 두고 주어진다(3≤N≤100,000, 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






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.