[JUNGOL #2268] 그레이 코드

출처: KOI 본선 2010 5번

난이도 (Personal): Platinum III - IV

태그: Bitmasking, Constructive

 

문제:

(a,b)와 (c,d)가 서로 붙어있는 그레이 코드 (매 인접한 수마다 비트가 하나씩만 다른 원형 배열)을 만들어라.

 

풀이:

 

일단 본문의 그레이 코드 예시를 살펴보자.

000 - 001 - 011 - 010 - 110 - 111 - 101 - 100

각 빨간색 위치는 어느 비트에서 달라지는지를 나타낸다. 편의상 1의 자리를 1번째 비트, 2의 자리를 2번째 비트, 4의 자리를 3번째 비트... 라고 하겠다.
그러면 순서대로 1 - 2 - 1 - 3 - 1 - 2 - 1인데, 이는 하노이 탑의 이동 순서와 동일함을 알 수 있다.
대체로 n개의 비트에 대해서 이 순서대로 움직이는 것이 그레이 코드를 생성함을 보일 수 있다.

또한, 모든 비트는 서로 대칭적인 구조를 가지므로 ABACABA... 순서만 따르면 어떤 비트를 먼저 뒤집는지 상관이 없다. 그리고 홀짝도 마찬가지므로 시작하는 값도 무관하다.

예시로 3 - 1 - 3 - 2 - 3 - 1 - 3로 010에서 시작 시

010 - 110 - 111 - 011 - 001 - 101 - 100 - 000

으로 그레이 코드가 됨을 볼 수 있다.

 

이제 예제를 다시 한 번 살펴보도록 하자.

1번째 비트가 바뀌는 짝은 다음과 같다.

000 - 001 - 011 - 010 - 110 - 111 - 101 - 100

1번째 비트가 2^3 / 2번 바뀌기에 가능한 모든 짝이 나타남을 볼 수 있다.

그리고 2번째 비트가 바뀌는 짝은 다음과 같다.

000 - 001 - 011 - 010 - 110 - 111 - 101 - 100

이 때 짝은 모든 홀수 (즉, 1번째 비트가 1인)인 지점을 점거하는데, 이는 2번째 비트가 2^3 / 4번 바뀌며, 2번째 비트가 바뀌는 모든 순간 사이에 1번째 비트가 2번 바뀌기 때문이다. (동일한 비트가 2번 바뀌면 원상태로 돌아온다.)

그러면 시작점을 0 대신 1로 바꾸면 어떻게 될까?

001 - 000 - 010 - 011 - 111 - 110 - 100 - 101

이러면 모든 짝수가 (즉, 1번째 비트가 0인) 2번째 비트가 달라지는 짝을 형성한다.

 

위와 마찬가지 방법으로 진행하면 된다.

예를 들어서 처음 짝이 P번째 비트, 그 다음 짝이 Q번째 비트에서 달라진다고 하자.

그러면 ABACABA... 패턴에서 A를 P로 두면, 처음 짝이 항상 나타남을 보장할 수 있다.

i) P = Q

이러면 두 번째 짝 역시 항상 나타남을 보장할 수 있다.

ii) P != Q

ABACABA... 패턴에서 B를 Q로 두면 Q번째 비트가 바뀌는 모든 짝은 P번째 비트가 모두 같다 (1이든가 0이든가.)

그러면 모든 수의 P번째 비트를 전환하면 그레이 코드가 유지되며, Q번째 비트가 바뀌는 모든 짝의 P번째 비트가 전환되므로 둘 중의 하나는 두 번째 짝을 항상 포함해야 한다.

 

예를 들어서, 주어진 짝들이 [1,3] (P = 2), [0,4] (Q = 3)이라 하자.

그러면 ABACABA... 패턴을 [2 (= P),3 (= Q),2,1,2,3,2]로 둘 시

000 - 010 - 110 - 100 - 101 - 111 - 011 - 001이 된다.

위와 같이 첫 번째 짝은 항상 포함된다.

그러나, 두 번째 짝이 포함되지 않으므로 모든 수의 2번째 비트를 뒤집는다.

그러면

010 - 000 - 100 - 110 - 111 - 101 - 001 - 011이 되어서, 두 번째 짝 역시 포함됨을 확인할 수 있다.

 

이제 입력 조건 (000...0으로 시작, 8개당 한 줄)만 맞춰서 출력하면 AC를 받을 수 있다.

 

풀이 소스코드:

 

def numm():
        return map(int,input().split())

        import sys
m,k=numm()
a,b=input().split()
a =int(a,2)
b=int(b,2)
c=a
d=b
K = abs(a-b)
L=K
if K.bit_count()!=1:
    print(-1)
    sys.exit()
if k>1:
    c,d=input().split()
    c =int(c,2)
    d=int(d,2)
    L=abs(c-d)
if L.bit_count()!=1:
    print(-1)
    sys.exit()
K = K.bit_length()-1
L = L.bit_length()-1
ar = [K,L]
if L==K:
    ar.pop()
for i in range(m):
    if i not in ar:
        ar.append(i)
ar2 = [a]
v = 0
for i in range(1,1<<m):
    B = i&(-i)
    B = B.bit_length()-1
    ar2.append(ar2[-1]^(1<<ar[B]))
for i in range(1<<m):
    if (ar2[i],ar2[i-1])==(c,d) or (ar2[i],ar2[i-1])==(d,c):
        v = 1
if not v:
    S = ar2[0]^ar2[1]
    for i in range(1<<m):
        ar2[i]^=S
ar3=[]
for i in range(1<<m):
    B = bin(ar2[i])[2:]
    B = (m-len(B))*'0'+B
    ar3.append(B)
PP = ar3.index('0'*m)
ar3 = ar3[PP:]+ar3[:PP]
for i,z in enumerate(ar3):
    print(z,end=' ')
    if i&7==7:
        print()