[Platinum IV] 불 끄기 - 14939
성능 요약
메모리: 114680 KB, 시간: 240 ms
분류
비트마스킹, 브루트포스 알고리즘, 그리디 알고리즘
제출 일자
2024년 4월 19일 17:07:51
문제 설명
전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라
입력
10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.
출력
모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.
풀이
import copy
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]
def isValid(arr, x, y) :
for d in range(5) :
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < 10 and 0 <= ny < 10 :
arr[nx][ny] = not arr[nx][ny]
def solve(arr) :
ans = float('inf')
for first_row in range(1<<10) : # 10개 전구에 대한 모든 조작 경우의 수
cnt = 0
narr = [copy.deepcopy(row) for row in arr] # arr 상태 복사
for i in range(10) :
if first_row & (1 << i) : # 첫 줄의 i번째 전구를 조작하는 경우
isValid(narr, 0, i)
cnt += 1
for i in range(1, 10) : # 나머지 줄 처리
for j in range(10) :
if narr[i-1][j] : # 위 전구가 켜져 있으면 해당 위치의 전구 조작
isValid(narr, i, j)
cnt += 1
if all(not val for row in narr for val in row) : # 모든 전구가 꺼져 있는지 확인
ans = min(ans, cnt)
return ans if ans != float('inf') else -1
arr = []
for _ in range(10) :
row = list(map(lambda x: x == 'O', input().strip()))
arr.append(row)
print(solve(arr))브루트 포스 알고리즘을 사용하여 문제를 해결할 수 있었다. 전구의 상태를 변경하는 방식 때문에, 첫 번째 줄의 전구를 켜고 끄는 방식이 전체 패턴에 영향을 미치고 있다. 따라서, 첫 번째 줄의 모든 가능한 조합을 시도해보고, 그에 따라 나머지 줄들을 조정해가며 전구를 모두 끄는 최소 행위 횟수를 찾아야 한다.
- 첫 번째 줄에 있는 각 전구에 대해 켜지거나 꺼질 수 있는 모든 경우의 수(2 ^ 10 = 1024가지)를 고려
- 각 경우에 대해, 첫 번째 줄의 설정을 바탕으로 나머지 줄들에서 전구를 끄는 방법을 찾는다. 이 때, 현재 줄의 바로 위에 있는 전구가 켜져 있다면, 해당 전구를 끄기 위해 현재 줄의 해당 위치에 있는 스위치를 눌러야 한다.
- 모든 전구를 끌 수 있는 경우, 스위치를 누른 횟수를 기록. 모든 경우를 시도한 뒤, 가장 적은 횟수를 찾는다.
- 만약 모든 경우를 다 했음에도 모든 전구를 끌 수 없다면, -1을 출력 (아마 101가지보다 가지수가 많다면)
코드 구현은 첫 번째 줄의 스위치 조작을 통해 생성되는 모든 패턴을 시뮬레이션하여 나머지 줄들을 조절하는 방식으로 진행하였다. 이 과정에서 2차원 배열을 사용하여 전구의 상태를 저장하고 업데이트하는 방식을 채택하였다. 또한, 각 단계에서 스위치를 누를때마다 상, 하, 좌, 우의 전구 상태를 변경하는 함수를 구현하였다.
문제를 해결하는데 있어 비트마스킹 활용하는 부분이나 구현하는 부분에 많은 어려움이 있어 구글 검색이나 GPT의 힘을 많이 빌렸다.