백준 14939번
오늘 풀어본 문제는 백준의 14939번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
(2024-06-05 수정: 원래 이 문제는 CLASS 5 문제였으나, solved.ac의 시즌 4 업데이트로 인해 CLASS 6 문제로 변경되었다.)
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
전구 $100$ 개가 $10 \times 10$ 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 $100$ 개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라
입력
$10$ 줄에 $10$ 글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.
출력
모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 $-1$ 를 출력하라.
풀이과정
1번째 시도
이 문제를 해결하기 위해 이용한 방법은 첫 번째 줄에 대한 모든 경우에 대하여 확인하고, 확인 과정에서 나머지 줄들은 윗 줄을 모두 끌 수 있는 방식으로 스위치를 누르도록 하여 최종 결과를 확인하도록 하는 것이었다. 이러한 방식의 풀이가 가능한 이유는 버튼들을 누르는 ‘순서’는 상관이 없기 때문이다.
첫 번째 줄의 각 경우마다, 확인이 끝나면 마지막 줄이 전부 불이 꺼져있는지 확인하고, 전부 꺼져있으면 최종 정답을 업데이트 하도록 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> lights(10, vector<bool>(10, false));
void rowClick(int row, unsigned rowInfo);
void click(int row, int col);
bool rowCheck(int row);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i=0; i<10; i++) {
string line;
cin >> line;
for (int j=0; j<10; j++) {
if (line[j] == 'O') {
lights[i][j] = true;
}
}
}
int minimum = INT_MAX;
for (int i=0; i<(1<<10); i++) {
int temp = 0;
queue<pair<int, int>> clicked;
rowClick(0, i);
for (int row = 1; row < 10; row++) {
for (int col = 0; col < 10; col++) {
if (lights[row - 1][col]) {
click(row, col);
clicked.emplace(row, col);
temp++;
}
}
}
if (rowCheck(9)) {
minimum = min(minimum, temp);
}
rowClick(0, i);
while (!clicked.empty()) {
pair<int, int> curr = clicked.front();
clicked.pop();
click(curr.first, curr.second);
}
}
if (minimum == INT_MAX) {
cout << -1;
}
else {
cout << minimum;
}
return 0;
}
void rowClick(int row, unsigned rowInfo) {
int col = 0;
while (rowInfo > 0) {
if (rowInfo % 2 == 1) {
click(row, col);
}
rowInfo >>= 1;
col++;
}
}
void click(int row, int col) {
lights[row][col] = !lights[row][col];
if (row > 0) {
lights[row - 1][col] = !lights[row - 1][col];
}
if (row < 9) {
lights[row + 1][col] = !lights[row + 1][col];
}
if (col > 0) {
lights[row][col - 1] = !lights[row][col - 1];
}
if (col < 9) {
lights[row][col + 1] = !lights[row][col + 1];
}
}
bool rowCheck(int row) {
for (int col=0; col<10; col++) {
if (lights[row][col]) {
return false;
}
}
return true;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
처음에는 전구 정보 배열을 복사하지 않고 복구하는 방식으로 구현했기 때문에 복구 과정에서 문제가 생겼나 싶어 매번 복사하는 식으로 변경하였다. 그러나 진짜 원인은 첫 번째 줄에서 누르는 버튼의 개수를 세어주지 않았던 것이었다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
void rowClick(int row, unsigned rowInfo, int &count, vector<vector<bool>> &lights);
void click(int row, int col, vector<vector<bool>> &lights);
bool rowCheck(int row, vector<vector<bool>> &lights);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<vector<bool>> lights(10, vector<bool>(10, false));
for (int i=0; i<10; i++) {
string line;
cin >> line;
for (int j=0; j<10; j++) {
if (line[j] == 'O') {
lights[i][j] = true;
}
}
}
int minimum = INT_MAX;
for (int i=0; i<(1<<10); i++) {
int temp = 0;
vector<vector<bool>> newLights(10, vector<bool>(10, false));
copy(lights.begin(), lights.end(), newLights.begin());
rowClick(0, i, temp, newLights);
for (int row = 1; row < 10; row++) {
for (int col = 0; col < 10; col++) {
if (newLights[row - 1][col]) {
click(row, col, newLights);
temp++;
}
}
}
if (rowCheck(9, newLights)) {
minimum = min(minimum, temp);
}
}
if (minimum == INT_MAX) {
cout << -1;
}
else {
cout << minimum;
}
return 0;
}
void rowClick(int row, unsigned rowInfo, int &count, vector<vector<bool>> &lights) {
int col = 0;
while (rowInfo > 0) {
if (rowInfo % 2 == 1) {
click(row, col, lights);
count++;
}
rowInfo >>= 1;
col++;
}
}
void click(int row, int col, vector<vector<bool>> &lights) {
lights[row][col] = !lights[row][col];
if (row > 0) {
lights[row - 1][col] = !lights[row - 1][col];
}
if (row < 9) {
lights[row + 1][col] = !lights[row + 1][col];
}
if (col > 0) {
lights[row][col - 1] = !lights[row][col - 1];
}
if (col < 9) {
lights[row][col + 1] = !lights[row][col + 1];
}
}
bool rowCheck(int row, vector<vector<bool>> &lights) {
for (int col=0; col<10; col++) {
if (lights[row][col]) {
return false;
}
}
return true;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
CLASS 5 에센셜 문제를 다 풀었다고 너무 기고만장했던 것 같다. CLASS 5 나머지 문제들을 시작하자마자 플래티넘 문제 5개가 기다리고 있던 것이다… 다시 CLASS 4 를 풀던 그 때의 초심으로 돌아가 겸손한 태도로 PS에 임해야겠다.
(2024-06-05 수정: 마무리 멘트가 이랬던 것은 이 문제를 푸는 것이 굉장히 어려웠기 때문이었는데, 역시 CLASS 5 문제라기엔 어려운 문제가 맞았던 모양이다!)
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/14939