[백준] 14989 - 불 끄기 💡 / 플래티넘 5 / 브루트포스 & 그리디

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

링크: https://www.acmicpc.net/problem/14939

문제

문제를 요약하자면, 10X10에 켜진 전구는 O로, 꺼진 전구는 X로 주어지는데, 전구의 스위치를 누르면 십자가 모양으로 해당 전구와 위, 아래, 왼쪽, 오른쪽 전구의 상태도 바뀝니다. 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치 개수를 출력해야 합니다.

 

1) 예제 입출력❄️

예제 입출력

예제를 보면, 맨 왼쪽 위와 맨 오른쪽 아래는 각각 1번씩 가운데 전구의 스위치를 눌러주면, 모두 꺼집니다. 가운데를 보면 가운데 ## 이렇게 되어있는데, 왼쪽 #을 누르면, 오른쪽에 켜진 전구가 십자가 모양이 되어 한번 더 눌러 모두 끌 수 있습니다. 그래서 총 4번 눌러 모든 전구를 끌 수 있습니다.

 

2. 핵심 논리☢️

핵심은 첫 번째 행에 전구 10개에 대해 켜고 끄는 모든 경우의 수 2^10=1024에 대해, 두 번째 행부터는 윗 행의 전구를 끄기 위한 스위치만 누르는 것입니다. 그러면 첫 번째 행의 전구 상태로 기준을 잡고, 다음 행부터 윗 행의 전구를 끄기 위해 눌러야만 하는 스위치만 누르기 때문에 전체 경우가 모두 고려됩니다. 진짜 어떻게 이런 생각을 했는지 대답합니다. (저는 풀다가 안 풀려서 답을 참고했습니다.)

 

3. 풀이 코드✅

1) 코드

from copy import deepcopy
arr0 = [list(input()) for _ in range(10)] # 전구배열 입력
dic = {'O':'#','#':'O'} # 스위치 켜고, 끄고 딕셔너리
res = 101 # 최종 출력값 초기화

for k in range(1024): # 첫 줄의 모든 경우수
    arr = deepcopy(arr0); cnt = 0 # 스위치 누른 횟수
    
    for j in range(10): # 첫줄에 10개 전구 하나씩 탐색
        if k&(1<<j):                                # j번째 스위치를 누른 경우(눌려있는 경우)
            cnt += 1                                # 스위치 누르기
            for r,c in (0,j-1),(0,j),(0,j+1),(1,j): # 맨 윗줄 4방향 보기
                if 0<=c<10:                         # 열이 삐져나가지 않은 경우
                    arr[r][c] = dic[arr[r][c]]      # 스위치 딸깍!
                    
    for i in range(9):         # 첫줄부터 9번째까지 (실제 스위치 누르는건 두번째행 부터 10번째 까지)
        for j in range(10):    # 10개 열
            if arr[i][j]=='O': # 윗 행에 불이 켜져있다면,
                cnt += 1       # 스위치 누르기
                for r,c in (i,j),(i+1,j-1),(i+1,j),(i+1,j+1),(i+2,j):
                    if r<10 and 0<=c<10: 
                        arr[r][c] = dic[arr[r][c]]
                        
    if all(c=='#' for c in arr[-1]): # 막줄에 모두 꺼진 경우
        res = min(res,cnt)
print(res if res<101 else -1)

처음에 전구 배열을 arr0에 입력받고, 스위치를 켜고 끄는 역할의 딕셔너리 dic을 정의하고, 최종 출력 값으로 쓰일 res를 101로 초기화합니다. res를 101로 초기화 하는 이유는 누른 스위치 개수의 최소값을 출력하는 것인데, 주어진 스위치는 최대 100개이니 101로 초기화를 합니다. 

첫 행의 전구 스위치를 누르는 모든 경우의 수는 2^10=1024입니다. 그렇게 첫 행의 모든 스위치를 누르는 경우의 수를 k로 받고, 전구 배열을 arr에 깊은 복사(deepcopy)를 해줍니다. deepcopy를 해주는 이유는 주어진 배열이 이중배열이기 때문에 단순 copy로는 arr의 값이 바뀌었을 때, arr0의 값도 바뀌기 때문입니다. (자세한 내용은 swallow copy, deep copy를 찾아보시면 됩니다.) 그렇게 첫 행의 스위치 누르는 경우를 k&(1<<j)를 이용해 arr에 반영해 줍니다. 이 부분은 아래에서 자세히 설명하겠습니다.

다음으로, for r,c in (0, j-1), (0, j), (0, j+1), (1, j): 를 통해 첫 행의 경우에 대해 스위치를 눌렀을 때를 반영해줍니다. 그렇게 첫 행의 전구 상태가 결정이 되면, 그다음으로 첫 번째 행부터 9번째 행의 상태를 보며, 그 아래 행인 두 번째 행부터 10번째 행에서 윗 행의 전구가 꺼지도록 스위치를 누르며 cnt+=1을 해줍니다. 전구 스위치를 누르는 경우 십자가 형태로 반영이 되며, 아래 그림에 첫 행의 경우와 그다음에 첫 번째 행부터 9번째 행의 스위치를 누르는 경우의 그림입니다.

스위치를 누르는 경우 반영되는 전구들 시각화

그리고, 마지막행 arr[-1]의 모든 전구가 불이 꺼져있다면, res=min(res, cnt)를 통해 최솟값 갱신을 해주면 됩니다. 최종적으로, res가 101 미만인 경우, 즉, 스위치를 눌러 모든 전구의 불을 끄는 게 가능한 경우 res(스위치 누른 횟수)를 출력하고, 그게 아닌 경우는 -1을 출력합니다.

 

2) 핵심 코드 부분

for j in range(10): # 첫줄에 10개 전구 하나씩 탐색
        if k&(1<<j):                                # j번째 스위치를 누른 경우(눌려있는 경우)
            cnt += 1                                # 스위치 누르기
            for r,c in (0,j-1),(0,j),(0,j+1),(1,j): # 맨 윗줄 4방향 보기
                if 0<=c<10:                         # 열이 삐져나가지 않은 경우
                    arr[r][c] = dic[arr[r][c]]      # 스위치 딸깍!

첫 줄에 스위치를 누를 때 사용된 k&(1<<j) 부분을 자세히 보겠습니다. 코드의 의미는 1을 j번만큼 shift 하여 2진수로 표현하고, k와 일치되는 부분만 and(&)를 통해 1로 하는 것입니다. 이 부분은 k가 0부터 1023 사이의 수이고, 이를 2진수로 표현하여 첫 행 10개의 전구 중에 몇 번째 전구를 누를지를 결정하는 부분입니다. 아래 k와 j의 for문과 함께 k&(1<<j)를 1과 0으로 출력해 봤습니다. 출력 결과를 보면 첫 행의 스위치를 누른 상태가 보입니다. 처음에는 아예 안 누른 경우, 그다음에는 첫 번째 전구의 스위치만 누른 경우,... 등으로 표현됩니다.

k&(1<<j) 시각화

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/14939_%EB%B6%88_%EB%81%84%EA%B8%B0.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/