백준 14939 - 불 끄기 [Python]

www.acmicpc.net/problem/14939

14939번: 불 끄기

 

비트마스킹

 

맨 윗줄은 2^10가지의 경우를 모두 테스트하고, 2번째 줄부터 그 위 전구가 켜져있으면 스위치를 누르는 방식으로 쭉 진행하면 된다.

 

그러고 마지막줄까지 진행한 후, 마지막줄에 켜져있는 전등이 있는지 확인하면 된다.

레퍼런스 당해서 힘들었다..

table = []
for i in range(10):
    temp = list(input())
    for j in range(10):
        if temp[j] == 'O':
            temp[j] = True #True: 불 켜져있음
            continue
        temp[j] = False #False: 불 꺼져있음
    table.append(temp)
 
dx = [-1, 1, 0, 0, 0]
dy = [0, 0, 0, -1, 1]
ans = 101
for f in range(1<<10):
    a = []
    for i in range(10):
        a.append(table[i][:])
    cnt = 0
 
    for i in range(10):
        if f & (1<<i): #i번째 스위치를 누른 경우
            cnt += 1
            for k in range(5):
                nx = i + dx[k]
                ny = 0 + dy[k]
                if 0 <= nx <= 9 and 0 <= ny <= 9:
                    a[ny][nx] = not a[ny][nx]
 
    for i in range(1, 10): #y좌표
        for j in range(10): #x좌표
            if not a[i-1][j]: #바로 윗 전등이 켜져있다면 스위치를 눌러줘야됨
                continue
            for k in range(5):
                nx = j + dx[k]
                ny = i + dy[k]
                if 0 <= nx <= 9 and 0 <= ny <= 9:
                    a[ny][nx] = not a[ny][nx]
            cnt += 1
 
 
    can = True
    for i in range(10):
        if a[9][i] == True:
            can = False
 
    if can:
        ans = min(cnt, ans)
 
print(ans if ans != 101 else -1)

비슷한 문제로 14927 - 전구 끄기 문제가 있다.

 

www.acmicpc.net/problem/14927

14927번: 전구 끄기

 

그냥 똑같이 하면 된다. 원래 table을 a로 가져올 때 deepcopy를 썼는데 이게 시간을 엄청 잡아먹는다고 한다. 그래서 방법을 바꿨다. 위 불 끄기 코드도 원래는 a = copy.deepcopy(table)이었다..

 

 

import sys
input = sys.stdin.readline
 
n = int(input())
table = []
for i in range(n):
    temp = list(map(int, input().split()))
    table.append(temp)
 
dx = [-1, 1, 0, 0, 0]
dy = [0, 0, 0, -1, 1]
ans = 1234
for f in range(1<<n):
    a=[]
    for i in range(n):
        a.append(table[i][:])
    cnt = 0
 
    for i in range(n):
        if f & (1<<i):
            cnt += 1
            for k in range(5):
                nx = i + dx[k]
                ny = 0 + dy[k]
                if 0 <= nx < n and 0 <= ny < n:
                    a[ny][nx] = not a[ny][nx]
 
    for i in range(1, n):
        for j in range(n):
            if a[i-1][j]:
                for k in range(5):
                    nx = j + dx[k]
                    ny = i + dy[k]
                    if 0 <= nx < n and 0 <= ny < n:
                        a[ny][nx] = not a[ny][nx]
                cnt += 1
 
 
    can = True
    for i in range(n):
        if a[-1][i] == True:
            can = False
            break
 
    if can:
        ans = min(cnt, ans)
 
print(ans if ans != 1234 else -1)

 

9초!

오타, 오류 지적 환영합니다.