[Bit Mask]BJ_14939, 불 끄기

[문제의 접근] 

 전구 100개가 10x10 모양으로 주어지는 input, 무엇을 떠올려야 할까? 10이하로 주어지는 모양을 보아서는 뭔가 bit mask나 DFS적인 접근이 될거라는 생각이 먼저 떠올라야 한다. 또한 기초적으로 생각해야 할 것들을 적어보자. 

 

 1) XOR 연산을 떠올려야 한다. 스위치를 누르면 불이 켜져있을 때는 꺼지게 되고, 불이 꺼져 있을 때는 켜지게 된다. 이는 곧 XOR연산을 의미한다. 0을 꺼짐, 1을 켜짐으로 명명한다고 하면 0 ^ 1 = 1, 1 ^ 1 = 0 이 되니 말이다. 

 

 2) (특징) 행렬의 제일 위에서 부터 불을 끄게 된다고 한다면 현재보다 위의 행에 불이 켜져 있다면 반드시 현재 행의 스위치를 눌러야 한다. 예를 들면 위의 예제 입력에서 좌측 상단을 (0, 0)이라고 하면 (1, 0)의 위치에서는 반드시 스위치를 눌러야 한다는 이야기다. 십자가 모양으로 불이 켜지거나 꺼지기 때문이다. 사실 이건 매우 재미있는 사실이다. 

 

 3) 모든 경우는 그럼 어떻게 생각해 볼 수 있을까? 위의 2번 특징으로 인해서 첫 번째 줄에서만 모든 경우의 수를 생각해 주면 된다. 두 번째 줄 부터는 첫 번째 줄에 불이 켜져있냐 꺼져있냐에 따라서 스위치 조작이 결정되기 때문이다. 그렇다면 첫 번 째 줄의 모든 경우의 수는? 여기에서 Bit mask를 사용하면 편하게 구현이 가능하다. 불이 켜져 있으면 1 꺼져 있으면 0으로 가정하고 bit mask배열로 0부터 $2^{10}$까지 for문으로 순회하면서 각 자리수에 1이 되어 있으면 스위치를 눌러야 함을 의미하는 것으로 모든 경우의 수를 표현할 수 있다. 

 

 4) 위의 흐름으로 생각해 보면 스위치를 한번 누른 곳은 다시 누르는 경우가 없는 것을 생각해 볼 수 있다. 그렇다면 최대 스위치 누르는 횟수는 100이 될 것이다. 

 

[문제의 구성] 

 다음과 같은 필수적인 함수를 확인해 보자.

 input으로 주어지는 string을 bit-mask를 이용하기 위해서 숫자로 표현한다. 모든 불이 꺼지면 0이 되고, 모든 불이 켜지면 $2^{10}-1=1023$이 되는 것이라고 생각하면 쉽다. 

 

def input_data():
    arr = []
    for i in range(10):
        temp = rdln().rstrip()
        tval = 0
        for j in range(10):
            if temp[j] == 'O':
                tval += 2**j
        arr.append(tval)
    return arr

 

  전체 배열이 0인 불이 꺼진 상태를 체크하는 함수이다. list a는 10개의 행을 나타내는 10개의 원소로 이루어져 있고, 각 줄의 값이 0이라면 True를 아니라면 False를 반환한다.

 

def check(a):
    for i in range(10):
        if a[i] != 0:
            return False
    return True

 

 불의 스위치를 켜는 동작을 하는 함수이다. XOR 연산으로 구성되어 있고, 범위를 체크하는 항목이 추가로 구현되어 있다. 

 

def light_on(t, y, x):
    t[y] = t[y]^(1<<x)
    if (y > 0): t[y-1] = t[y-1]^(1<<x)
    if (y < 9): t[y+1] = t[y+1]^(1<<x)
    if (x > 0): t[y] = t[y]^(1<<(x-1))
    if (x < 9): t[y] = t[y]^(1<<(x+1))

 

 Main solving 함수. bit mask를 이용해서 첫 째 행에 대해서 어느 자리에 불을 켜야하는지  0부터, 1<<10까지 전체 탐색을 진행한다. 첫 째 행은 이 bit mask에 따라서 불을 켜는 동작을 1차로 수행하고, 2번째 줄에서 부터 10번 째 줄까지는 위의 행에 불이 켜져있는지 확인해서 스위치를 켜는 동작을 구현한다. 스위치를 켜는 횟수는 cnt로 체크하고 불이 전체가 다 꺼진 케이스에 대해서는 ans와의 min 함수 비교를 통해서 확인 할 수 있다. 

 

def solve():
    # 첫번째 행에 대해서 전구를 켤수 있는 경우의 수에 대해 전탐색을 진행하고
    # 이 후 열은 위의 열의 불을 끄는데 집중해서 진행한다. 아래에서 끄지 않으면 불을 끌 수 없기 때문에.
    ans = 200 # 똑같은 자리를 2번 누르는 것은 원래 상태로 돌아가기 때문에 낭비 행위, 대략 2배로 설정
    for bit in range(0, 1<<10):
        t_arr = arr.copy()
        cnt = 0
        # 첫번째 행에 대한 계산 먼저 수행, 모든
        for i in range(10):
            if bit & (1<<i):
                cnt += 1
                light_on(t_arr, 0, i)
        # 이후 계산은 이전 행에 켜져 있는 불을 끄면서 진행해야 한다.
        for y in range(1, 10): # 행에 대한 체크, 두 번째 행에서 부터 시작
            for x in range(0, 10): # 열에 대한 체크
                if (t_arr[y-1] & (1<<x)):
                    cnt += 1
                    light_on(t_arr, y, x)
        
        if check(t_arr): # 불이 다 꺼져 있는지 확인
            ans = min(ans, cnt)
    if ans == 200: # 방법이 없다면 -1을 출력
        return -1
    return ans

 최종적으로 풀이를 제출한 결과는 python으로 진행했음에도 시간이 많이 소요되지 않는 것을 확인할 수 있다. 이 문제의 어려운 점은 스위치를 몇 번 반복적으로 켜야하는지, 어디서 부터 진행해야 하는지를 생각하지 못한 경우에는 무한한 가능성을 가진 문제라고 느껴져 접근이 어려울 수 있다. 이 때에는 어떻게 해야 스위치의 시작 위치를 확정하고 반복적으로 얼마나 진행해야 하는지를 생각해 보는 것이 중요하다. 

최종 코드는 아래를 참고하자. 

 

https://github.com/Koo82/Algotirhm/blob/main/%5BBIM%5DBJ_14939.py

GitHub - Koo82/Algotirhm