14939🐨불 끄기-파이썬

불 끄기

시간 제한	메모리 제한
1 초	128 MB

문제

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라

입력

10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.

출력

모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.

예제 입력 및 출력

#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#

4

---

https://sites.google.com/view/bulbgame/home

전구 게임

 

왼쪽의 예제 1을 보면 4번만에 해결할 수 있다는 것을 알 수 있다.
그리고 오른쪽의 예를 보면 불이 켜진 전등의 아래 전등을 누르는 식으로 불이 켜진 구역을 쓸듯이 아래로 내려서 전등의 개수를 줄일 수 있다는 것을 알 수 있다. 전등이 켜진 곳을 옮길 수 있다면 모서리로 몰아가면 개수를 줄일 수 있는 것이다.

그런데 오른쪽 예에서 마지막 줄에 남아 있는 전구들은 끌 수 있는 방법이 없다. 그 아래를 누를 수 없기 때문에 해당 전구나 주위를 직접 눌러야 하며, 그렇게 하면 켜진 전구가 다시 윗 줄로 전파되기 때문에 루프에 걸리게 된다.
그렇다면 9번째 줄을 누르고 났을 때 마지막 줄에 켜진 전구가 남아있다면 불가능한 것이다.

여기까지 아이디어를 가지고 코드를 짰다. 굉장히 짜기 쉬웠다.
당연히 오답 코드였다.

def targets(x,y):
    return [(x+dx,y+dy) for dx,dy in zip([-1,0,1,0],[1,1,1,2]) if 0<=x+dx<10 and 0<=y+dy<10]

count=0
a=[*map(bytearray,open(0,'rb').read().split())]
for i in range(9):
    for j in range(10):
        if a[i][j]==79:
            t=targets(j,i)
            for tx,ty in t:
                a[ty][tx]=35 if a[ty][tx]==79 else 79
            count+=1
s=sum(a[9][k]==79 for k in range(10))

print(-1 if s else count)

동작은 간단하게 9번째 줄까지 돌면서 켜져 있으면 그 아래의 T자 모양 범위를 반전시키고 지나가는 것이다. targets 함수가 대상 좌표를 생성한다. 그리고 켜져 있는 전구의 개수를 센다. 마지막 줄의 전구가 하나라도 남아 있으면 실패다. 만약 마지막 줄이 다 꺼져 있다면 위에서 발견한 켜져 있는 전구의 수가 바로 답이 된다.

이 코드는 8%에서 틀렸습니다를 받았는데 왜 틀렸는지를 곧 깨닫게 되었다.

첫째, 이 문제는 최소 횟수를 찾는 문제이므로 위 규칙을 적용하면 다음과 같은 반례가 있을 수 있다.

규칙대로 위 그림처럼 3 번을 눌렀는데도 처음 5개의 전구가 하나도 꺼지지 않고 아래로 이동한 것을 볼 수 있다.
하지만 실제로는 이렇게 해결할 수 있다.

이렇게 2번 만에 5개를 모두 끌 수 있다.
문제는 첫 줄에서 어떤 것을 누르느냐 안 누르느냐에 따라 아랫줄에 파급 효과를 주는데 나는 첫 줄을 하나도 안 누르고 성공하는 경우만 찾은 것이다. 심지어 첫 줄에 전등이 들어와 있나 아닌가와 상관없이 일부러 켜야 최소 횟수로 해결되는 경우도 생긴다.
두번째 줄 부터는 처음 생각한 규칙(켜져 있으면 그 아래 버튼 누르기) 최선이다.왜나하면 아래 버튼이 아니라 해당 버튼을 누르면 다시 전구가 위로 전파되기 때문에 최선의 해를 구할 수 없다.
그렇다면 첫 줄의 10개의 전구에 대해 끄고 켜는 모든 경우의 수를 생각해 보면 2의 10승이며 켤지 끌 지를 비트마스킹으로 조합을 만들어 풀 수 있다.

내가 제출한 것 중 가장 빠른 코드를 살펴보자

def s():
    count_min = float('inf')
    a = list(bytearray(i) for i in open(0, 'rb').read().split())
    
    for first_row in range(1 << 10):
        temp = [row.copy() for row in a]
        count = first_row.bit_count()
    
        for j in range(10):
            if first_row & (1 << j):
                for tx, ty in [(j+dx,dy) for dx,dy in [(0,0),(0,1),(-1,0),(1,0)] if 0<=j+dx<10]:
                    temp[ty][tx] = 35 if temp[ty][tx] == 79 else 79
    
        for i in range(1, 10):
            for j in range(10):
                if temp[i - 1][j] == 79:
                    for tx, ty in [(j+dx,i+dy) for dx,dy in [(0,0),(0,1),(0,-1),(-1,0),(1,0)]
                if 0<=j+dx<10 and 0<=i+dy<10]:
                        temp[ty][tx] = 35 if temp[ty][tx] == 79 else 79
                    count += 1
    
        if sum(temp[9]) == 350:
            count_min = min(count_min, count)
    
    print(-1 if count_min == float('inf') else count_min)
s()

코드 해설

1. 입력 데이터 읽기

코드의 첫 부분에서는 입력을 바이트 배열 형태로 읽어 들여 2차원 리스트 a에 저장합니다.

a = list(bytearray(i) for i in open(0, 'rb').read().split())

설명:
입력을 바이너리 모드로 읽고 각 줄을 bytearray로 변환합니다.
문자 #와 O의 아스키 값(35, 79)을 이용하여 전구의 꺼짐/켜짐 상태를 표현합니다.

---

2. 첫 번째 행의 모든 경우의 수 탐색

전체 10개의 전구에 대해 각 스위치의 누름 여부는 이진수로 표현할 수 있으므로, range(1 << 10) (즉 0부터 1023까지)을 이용해 모든 경우를 탐색합니다.
for first_row in range(1 << 10):

• 설명:
  각 first_row 값은 첫 번째 행에서 어떤 전구의 스위치를 누를지를 나타냅니다.
  예를 들어, 비트 1은 해당 위치의 스위치를 누른다는 의미입니다.

또한, 첫 행에서 누른 스위치 개수를 count = first_row.bit_count()와 같이 계산합니다.

---

3. 첫 행 스위치 적용

첫 행의 스위치 누름 조합에 따라 해당 전구와 인접 전구의 상태를 반전시킵니다.

for j in range(10):
    if first_row & (1 << j):
        for tx, ty in [(j+dx, dy) for dx, dy in [(0,0), (0,1), (-1,0), (1,0)] if 0 <= j+dx < 10]:
            temp[ty][tx] = 35 if temp[ty][tx] == 79 else 79

• 설명:
  • if first_row & (1 << j):
    해당 열 j의 스위치를 누른 경우를 확인합니다.
  • 리스트 내포를 사용하여 (tx, ty)로 인접 좌표를 구합니다.
    여기서 (0,0)은 자기 자신, (0,1)은 아래, (-1,0)과 (1,0)은 왼쪽과 오른쪽 전구를 의미합니다.
  • 조건문 if 0<=j+dx<10를 통해 인덱스 범위를 벗어나지 않도록 합니다.
  • 전구 상태는 아스키 코드 값으로 표현되며, 79는 ‘O’(켜짐), 35는 ‘#’ (꺼짐)입니다. 따라서 조건에 따라 반전합니다.
• 사실 두 문자가 홀수와 짝수이면 &1연산으로 하려고 바이트로 읽었는데... 둘 다 홀수여서 아쉬웠습니다. 
  비트 연산으로 검사한다면 &4로 검사할 수 있고(속도차이 없음)
                      temp[ty][tx] +=44-(22*(temp[ty][tx]&4)
  위 수식으로 35와 79를 바로 바꿔치기 할 수도 있습니다.(이건 오히려 삼항연산자보다 느린 건 비밀!)

---

4. 나머지 행 처리

첫 행이 결정된 후, 두 번째 행부터 마지막 행까지는 바로 위 행의 상태를 보고 결정합니다.
즉, 바로 위 행에 켜진 전구(79)가 있으면, 해당 전구를 끄기 위해 현재 행의 같은 열 스위치를 누릅니다.

for i in range(1, 10):
    for j in range(10):
        if temp[i - 1][j] == 79:
            for tx, ty in [(j+dx, i+dy) for dx, dy in [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0)] if 0 <= j+dx < 10 and 0 <= i+dy < 10]:
                temp[ty][tx] = 35 if temp[ty][tx] == 79 else 79
            count += 1

• 설명:
  • if temp[i - 1][j] == 79:
    바로 위 행의 전구가 켜진 상태라면,
  • 현재 행 i의 열 j 스위치를 누릅니다.
  • 이 때도 인접 전구(자기자신, 위, 아래, 좌, 우)의 상태를 반전시키며,
  • 동시에 스위치를 누른 횟수를 count에 누적합니다.

---

5. 결과 검증 및 최소 횟수 업데이트

마지막 행을 처리한 후, 전체 전구가 꺼졌는지 확인합니다.
if sum(temp[9]) == 350: count_min = min(count_min, count)

• 설명:
  • temp[9]는 마지막 행의 상태를 의미하며,
  • 전구가 꺼진 상태(#)는 아스키 코드 35입니다.
    10개 전구의 합이 35×10 = 350이면 모두 꺼진 것입니다.
  • 모든 경우 중 최소 스위치 누름 횟수를 count_min에 업데이트합니다.

---

6. 최종 출력

모든 경우를 탐색한 후, 유효한 해답이 존재하면 최소 횟수를 출력하고, 없으면 -1을 출력합니다.
print(-1 if count_min == float('inf') else count_min)

• 설명:

초기값을 float('inf')로 두었으므로, 해답이 한 번도 갱신되지 않았다면 불가능한 경우로 판단합니다.

가장 빠른 코드를 살펴보았는데 행렬로 풀었다....

 

# 입력 처리: '#' -> 0, 'O' -> 1
def input_lights():
    lights = []
    for _ in range(10):
        lights.append([0 if light == '#' else 1 for light in input().strip()])
    return lights

# 가우스 소거법을 사용하여 문제를 해결하는 함수
def gaussian_elimination(matrix, b):
    # 가우스 소거법을 통해 상삼각 행렬로 변환
    for i in range(100):
        if matrix[i][i] == 0:
            for j in range(i + 1, 100):
                if matrix[j][i] == 1:
                    matrix[i], matrix[j] = matrix[j], matrix[i]
                    b[i], b[j] = b[j], b[i]
                    break
        if matrix[i][i] == 0:
            continue
        for j in range(i + 1, 100):
            if matrix[j][i] == 1:
                for k in range(i, 100):
                    matrix[j][k] ^= matrix[i][k]
                b[j] ^= b[i]

    # 뒤에서부터 해를 구해가는 방식
    x = [0] * 100
    for i in range(99, -1, -1):
        x[i] = b[i]
        for j in range(i + 1, 100):
            x[i] ^= matrix[i][j] * x[j]

    return x

def solve_lights_out_with_gaussian():
    lights = input_lights()
    matrix = [[0] * 100 for _ in range(100)]
    b = [0] * 100

    # 버튼을 누를 때 영향 받는 칸을 표시하는 100x100 행렬 구성
    for r in range(10):
        for c in range(10):
            idx = r * 10 + c
            matrix[idx][idx] = 1
            if r > 0: matrix[idx][(r-1) * 10 + c] = 1  # 위쪽
            if r < 9: matrix[idx][(r+1) * 10 + c] = 1  # 아래쪽
            if c > 0: matrix[idx][r * 10 + (c-1)] = 1  # 왼쪽
            if c < 9: matrix[idx][r * 10 + (c+1)] = 1  # 오른쪽
            b[idx] = lights[r][c]  # 목표 상태 (켜져 있으면 1)

    # 가우스 소거법으로 해 찾기
    x = gaussian_elimination(matrix, b)
    
    # 버튼 누름 횟수 계산
    return sum(x)

# 실행
print(solve_lights_out_with_gaussian())

이해할 수 없어서 GPT에게 설명을 요구했습니다....

1. 문제 모델링

이 문제는 $10\times10$ 격자에서 전구가 켜져 있거나 꺼져 있는 상태를 다루며, 각 버튼(또는 스위치)을 누르면 해당 전구와 인접한 전구들의 상태가 반전됩니다. 이를 선형대수학적으로 모델링할 수 있습니다.

변수와 상태

• 각 격자 칸을 $i$ (총 100개, $i = 0, 1, \dots, 99$)에 대응시킵니다.
• 전구의 상태를 벡터 $\mathbf{b} \in {0,1}^{100}$로 나타냅니다.
  • $b_i = 1$이면 해당 전구가 켜져 있고, $b_i = 0$이면 꺼져 있음을 의미합니다.
• 각 버튼을 누르는 여부를 $x_i \in {0,1}$로 정의합니다.
  • $x_i = 1$이면 해당 위치의 버튼을 누른다는 의미이고, $x_i = 0$이면 누르지 않는다는 의미입니다.

버튼 효과 행렬

버튼을 누르면 영향을 주는 전구들을 고려하여 $100\times100$ 행렬 $A$를 구성합니다.

• $A_{ij} = 1$이면, 버튼 $j$를 누름으로써 전구 $i$의 상태가 반전됨을 의미합니다.
• $A_{ij} = 0$이면 버튼 $j$는 전구 $i$에 영향을 주지 않습니다.

구성 예시:

각 전구 $i$는 격자 상의 $(r, c)$로 표현할 수 있으며,

$$i = r \times 10 + c \quad (0 \le r, c \le 9)$$

입니다. 버튼 $j$ 또한 격자상의 $(r', c')$에 대응되며, 전구 $i$에 영향을 주는 버튼 $j$는 다음과 같습니다:

• 자기 자신: $(r, c)$
• 위쪽: $(r-1, c)$ (단, $r > 0$)
• 아래쪽: $(r+1, c)$ (단, $r < 9$)
• 왼쪽: $(r, c-1)$ (단, $c > 0$)
• 오른쪽: $(r, c+1)$ (단, $c < 9$)

따라서, 행렬 $A$의 각 행은 해당 전구에 영향을 주는 버튼들의 위치에 대해 $1$의 값을 갖게 됩니다.

---

2. 선형 시스템 구성

퍼즐을 해결한다는 것은, 초기 상태 $\mathbf{b}$를 모두 $0$ (즉, 모든 전구 꺼짐)으로 만드는 버튼 누름 $\mathbf{x}$를 찾는 것입니다. 전구 상태는 버튼의 누름에 의해 반전되므로, GF(2) (즉, $\mathbb{F}_2$)에서의 연산으로 표현할 수 있습니다.

수식으로 나타내면 다음과 같습니다:

$$A \cdot \mathbf{x} = \mathbf{b} \quad (\text{mod } 2)$$

여기서,

• $A$는 $100\times100$ 이진 행렬 (각 원소는 $0$ 또는 $1$),
• $\mathbf{x}$는 $100$차원 이진 벡터 (각 위치가 $0$ 또는 $1$),
• $\mathbf{b}$는 초기 전구 상태를 나타내는 이진 벡터입니다.

GF(2) 체에서는 덧셈이 XOR 연산과 동일하고, 곱셈은 일반 곱셈과 동일하게 작동합니다.

---

3. 가우스 소거법 (Gaussian Elimination) in GF(2)

전진 소거 (Forward Elimination)

1. 피벗 찾기 및 행 교환:
   각 단계 $i$에서, $A_{ii}$가 $0$이면 $i$보다 큰 인덱스의 행 중 $A_{ji} = 1$인 행 $j$를 찾아 서로 교환합니다. 이때 $\mathbf{b}$의 해당 원소도 같이 교환합니다.
2. 행 소거:
   만약 $A_{ii} = 1$이면, $i+1$번째 행부터 $100$번째 행까지, 해당 열 $i$의 원소가 $1$인 경우 현재 행을 XOR 연산(즉, 모듈로 $2$ 덧셈)을 통해 제거합니다. $$\text{For each } j > i \text{ with } A_{ji} = 1: \quad A_{j,k} \leftarrow A_{j,k} \oplus A_{i,k} \quad (k=i, \dots, 99)$$ $$b_j \leftarrow b_j \oplus b_i$$ 여기서 $\oplus$는 XOR (즉, 모듈로 $2$ 덧셈)을 의미합니다. .

역행 대입 (Back Substitution)

전진 소거 후에는 행렬 $A$가 상삼각 행렬(또는 계단식 행렬) 형태가 됩니다. 뒤에서부터 해를 구하는 방식은 다음과 같습니다.

1. 마지막 행부터 시작하여, 
   $$x_i = b_i \oplus \left( \bigoplus_{j=i+1}^{99} A_{ij} \cdot x_j \right)$$
   여기서 $\bigoplus$는 해당 항들에 대해 XOR 연산을 수행함을 의미합니다.

이 방식으로 $\mathbf{x}$를 모두 구하면, 이는 퍼즐을 해결하기 위한 버튼 누름 여부를 나타냅니다.

---

4. 알고리즘 적용 및 결과 해석

• 행렬 $A$ 구성:
  코드에서는 이중 반복문을 통해 각 격자 칸에 대해 자기 자신과 인접한 칸(위, 아래, 좌, 우)에 대해 행렬의 해당 원소를 $1$로 설정합니다.
• 우변 $\mathbf{b}$ 설정:
  각 칸의 초기 상태를 읽어, 전구가 켜져 있으면 $1$, 꺼져 있으면 $0$으로 벡터 $\mathbf{b}$를 구성합니다.
• 가우스 소거법 실행:
  gaussian_elimination(matrix, b) 함수는 위에서 설명한 절차대로 행렬 $A$와 벡터 $\mathbf{b}$에 대해 가우스 소거법을 적용하여 해 $\mathbf{x}$를 구합니다.
• 해의 검증 및 해석:
  구해진 $\mathbf{x}$의 각 성분은 버튼을 눌러야 하면 $1$, 그렇지 않으면 $0$입니다. 최종적으로 버튼을 누른 횟수는 $\sum_{i=0}^{99} x_i$로 계산됩니다.
  
  

---

5. 결론

이 알고리즘은 다음의 과정을 통해 문제를 해결합니다:

1. 입력 변환:
   입력된 '#'와 'O'를 각각 $0$과 $1$로 변환하여 초기 상태 벡터 $\mathbf{b}$를 구성합니다.
2. 행렬 $A$ 구성:
   각 버튼의 작용(자기 자신과 인접한 전구 반전)을 나타내는 $100\times100$ 이진 행렬 $A$를 만듭니다.
3. 선형 시스템 $A\mathbf{x} = \mathbf{b}$ 풀기:
   GF(2)에서 가우스 소거법을 사용하여 $\mathbf{x}$를 구합니다. 이때, 모든 연산은 XOR을 사용하여 처리됩니다.
4. 결과 해석:
   구한 $\mathbf{x}$에서 $1$의 개수를 세어 최소 버튼 누름 횟수를 반환합니다.