그레이 코드
시간 제한1초메모리 제한128 MB
M비트 순환 그레이 코드에서 주어진 한두 쌍이 반드시 이웃하도록 전체 순서를 구성하거나 불가능함을 판단하는 문제입니다.
문제
M비트 이진 문자열 2^M개를 모두 한 번씩 나열하되, 이웃한 두 문자열이 정확히 한 비트만 다르면 그 나열을 순환 그레이 코드라고 한다. 마지막 문자열과 첫 번째 문자열도 이웃으로 보며, 두 문자열은 한 비트만 달라야 한다. 3비트에서는 000, 001, 011, 010, 110, 111, 101, 100 순서가 이런 코드가 될 수 있다.
어떤 문자열은 한 비트만 다른 문자열이 여러 개 있다. 그러나 주어진 순환 그레이 코드 안에서 실제로 이웃하는 문자열은 그중 두 개뿐이다.
한 비트만 다른 문자열 쌍이 하나 또는 두 개 주어진다. 모든 주어진 쌍이 서로 이웃하도록 하는 순환 그레이 코드가 존재하는지 판단하고, 존재하면 그런 코드를 하나 출력하라.
입력
첫째 줄에 코드의 비트 수 M과 이웃해야 하는 문자열 쌍의 수 K가 주어진다.
- 3 <= M <= 15
- 1 <= K <= 2
다음 K개 줄에는 이웃해야 하는 두 M비트 이진 문자열이 공백으로 구분되어 주어진다. 각 쌍의 두 문자열은 정확히 한 비트만 다르다.
출력
조건을 만족하는 순환 그레이 코드가 존재하면, 00...0부터 시작하여 모든 코드를 순서대로 출력한다. 한 줄에는 코드 8개를 공백으로 구분해 출력하므로 전체 출력은 2^(M-3)줄이다. 가능한 답이 여러 개라면 아무거나 하나만 출력해도 된다.
조건을 만족하는 코드가 존재하지 않으면 -1을 출력한다.