백준 문제풀이
백준 14939 - 불 끄기 [Python]
Vermeil
2020. 12. 25. 17:48
14939번: 불 끄기
전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄
www.acmicpc.net
비트마스킹
맨 윗줄은 2^10가지의 경우를 모두 테스트하고, 2번째 줄부터 그 위 전구가 켜져있으면 스위치를 누르는 방식으로 쭉 진행하면 된다.
그러고 마지막줄까지 진행한 후, 마지막줄에 켜져있는 전등이 있는지 확인하면 된다.
레퍼런스 당해서 힘들었다..
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
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)
|
cs |
비슷한 문제로 14927 - 전구 끄기 문제가 있다.
14927번: 전구 끄기
홍익이는 N x N 전구 판을 가지고 있다. 전구 판에는 각 칸마다 전구가 하나씩 연결되어 있다. 이 전구 판에서 하나의 전구를 누르면, 해당 전구를 포함하여 상하좌우의 총 5개 전구들의 상태가 변
www.acmicpc.net
그냥 똑같이 하면 된다. 원래 table을 a로 가져올 때 deepcopy를 썼는데 이게 시간을 엄청 잡아먹는다고 한다. 그래서 방법을 바꿨다. 위 불 끄기 코드도 원래는 a = copy.deepcopy(table)이었다..
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
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)
|
cs |
오타, 오류 지적 환영합니다.