[BOJ] 14939 불 끄기 (C/C++)

14939번: 불 끄기

문제

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

입력

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

출력

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

---

오랜만에 그리디 문제를 풀었다. 그리디는 처음 배울 때에는 세상 만만해보이는데 막상 문제를 풀다보면 그 순간 순간에 어떤 행동이 최적인지 알아내는게 생각보다 어렵다. 심지어 이건 세상 만만한 완전 탐색도 끼어있음에도 그리 쉽지 않았다.

 

문제의 핵심은

1. 최소로 누르는 경우엔 뭘 먼저 누르던지 상관없음. 즉 순서는 상관없으므로 위에서부터 처리해나가면 된다.

2. 지금 (i, j) 번째 전구를 보고 있는 상황에서는 그 위의 전구가 켜져있는지를 궁금해한다. 위에서 아래로 내려가기 때문에 (i-1, j) 전구가 켜져있으면 지금밖에 끌 수 있는 기회가 없음. 따라서 첫 줄 전구의 상태만 어떻게 한다면 그 이후로는 그냥 내려가기만 하면 된다.

 

첫 줄 전구 상태를 정하기 위해서 비트마스킹을 사용했다. 전구가 10개밖에 되지 않기 때문에 2^10은 해봤자 1024다. 다른 문제를 풀면서도 비트마스킹 생각을 하긴하는데 숫자가 크면 막 2^100 이렇게 되어버리니까 아무데나 적용할 수 없었다. 그래도 이 문제는 10밖에 되지 않는다.

 

각 케이스마다 원상 복구, 모든 전구가 꺼졌는 지 검사하는걸 이중 for문을 사용해서 할 수도 있었지만, memcpy, memcmp 함수를 한번 사용해봤다. 이게 더 빠를지 아닐 지는 모르겠지만 코드가 깔끔해지긴 했다. 대신 이 함수들은 사용할 때 크기를 잘 정해줘야 된다. 아니면 어떤 문제가 생길 지 모른다.

 

 

후기)

오늘 코로나가 의심돼서 PCR 검사를 받고 왔다. 막 아픈건 아닌데 컨디션이 좋지는 않다. 내일 아침에 결과 나온다니 기다려봐야지.