https://www.acmicpc.net/problem/14939
| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라
입력
10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.
출력
모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.
풀이
전구 하나를 조작하는 상황을 생각해봅시다. 전구와 인접한 4개의 전구까지 5개의 전구가 반전됩니다. 2번 누르면 다시 원래대로 돌아옵니다. 다른 전구를 아무리 건드려도 이 전구를 두 번 건드린 결과는 전체 과정에서 이 전구를 건드리지 않는 것과 같습니다. 따라서 어떤 전구를 두 번 이상 조작할 필요가 없습니다. 각각의 전구에 대해 최대 1번씩, 모든 전구에 대해 총 100번의 조작이 최대치입니다. 그러면 이제 100개의 전구에 대해 조작할 것인지, 말 것인지만 생각하면 됩니다. 모든 경우를 따져보면 2100가지가 됩니다.
주어진 예제 상황을 살펴보기 전에 탐색 과정을 생각해봅시다. 가장 왼쪽 위에 있는 전구를 조작할 수 있는 전구는 3개 뿐입니다.
모든 전구를 딱 한 번까지만 조작할 수 있기 때문에 이 전구를 어떤 식으로든 조작한 후에 이 전구를 건드릴 방법은 그 전구의 아래, 오른쪽에 있던 전구 뿐입니다. 탐색 순서를 이렇게 정해봅시다.
대각선으로 한 줄씩 확인한다고 하면, 가장 첫 칸의 전구만 어떻게 할 것인지 결정해주면 그 뒤의 전구들은 조작 방법이 결정됩니다. 왜냐면 그 전구의 왼쪽 전구가 켜져있다고 하면 반드시 그 전구를 조작해야 마지막으로 왼쪽 전구를 끌 수 있기 때문입니다. 이렇게 조작 순서를 결정해 어떤 전구의 상태가 다른 전구의 상태를 강제하도록 할 수 있습니다. 그런데 탐색 방향이 이렇게 되어있으면 매번 탐색 길이도 바뀌어야 하고 10번째 대각선 이후로는 가장 왼쪽 칸이 하나씩 사라지는 것도 고려해야 합니다.
탐색 방향을 이렇게 해봅시다. 이렇게 탐색하면 가장 윗줄의 10개의 전구만 어떻게 조작할 것인지 결정해주면 그 아래의 모든 전구들은 바로 윗칸의 전구의 상태로 조작이 강제됩니다. 윗칸의 켜져있다면 조작해야 하고, 꺼져있다면 조작하지 않아야 합니다.
10개의 전구만 조작을 결정해주면 되므로 경우의 수는 1024가지로 압축되었습니다. 가장 윗줄 전구의 조작 여부를 0~1023범위의 비트로 관리할 수 있습니다. 그 다음 줄부터는 조작 여부를 이렇게 판단할 수 있습니다.
i행 j열의 전구의 조작 여부를 확인하기 위해 두 개의 2차원 배열이 필요합니다. 우선 원래 전구의 상태를 관리하는 bulb배열과 각 전구의 조작 여부를 관리하는 switch배열을 만듭니다. switch[i][j]의 값은 bulb[i - 1][j]가 현재 켜져있는지 아닌지 확인합니다. 이 값은 빨간색으로 표시된 주변 전구와 switch[i - 1][j]의 조작 여부를 확인합니다.
if bulb[i - 1][j] ^ switch[i - 1][j] ^ switch[i - 1][j - 1] ^ switch[i - 1][j + 1] ^ switch[i - 2][j]:
switch[i][j] = 1
xor 연산을 활용하면 1의 갯수를 세어 홀수인 경우 조작해 끄게 할 수 있고 짝수인 경우 조작하지 않습니다. switch[i][j] = 1이 나올 때마다 count를 1씩 증가시켜줍니다. 가장 마지막 전구인 switch[10][10]을 확인할 때, bulb[10][10] ^ switch[9][10] ^ switch[10][9] ^ switch[10][10] 값이 1이 나온다면 첫줄의 설정이 잘못된 것이므로 결과를 101로 반환합니다. 그렇지 않으면 count를 기존 값과 비교해 더 작은 값으로 갱신시킵니다.
정답 코드
import sys
input = sys.stdin.readline
bulb = [[0] * 12 for _ in range(12)]
for i in range(1, 11):
line = input().strip()
for j in range(10):
if line[j] == 'O':
bulb[i][j + 1] = 1
def switching():
res = 101
for b in range(1 << 10):
switch = [[0] * 12 for _ in range(12)]
d = 1 << 9
count = 0
for i in range(1, 11):
if b & d:
switch[1][i] = 1
count += 1
d >>= 1
for i in range(2, 10):
for j in range(1, 11):
if bulb[i - 1][j] ^ switch[i - 1][j - 1] ^ switch[i - 1][j] ^ switch[i - 1][j + 1] ^ switch[i - 2][j]:
count += 1
switch[i][j] = 1
if count >= res: break
if count >= res: break
if count >= res: continue
if bulb[9][1] ^ switch[9][1] ^ switch[9][2] ^ switch[8][1]:
count += 1
switch[10][1] = 1
for j in range(2, 11):
if bulb[9][j] ^ switch[9][j - 1] ^ switch[9][j] ^ switch[9][j + 1] ^ switch[8][j]:
count += 1
switch[10][j] = 1
if bulb[10][j - 1] ^ switch[9][j - 1] ^ switch[10][j - 1] ^ switch[10][j] ^ switch[10][j - 2]:
count = 101
break
if bulb[10][10] ^ switch[10][9] ^ switch[9][10] ^ switch[10][10]:
continue
if res > count:
res = count
print(res if res <= 100 else -1)
switching()
