SW Expert Academy 14413_격자판 칠하기 문제풀이 in C++
문제 URL
문제 요구사항
- N X M 크기의 직사각형 격자판이 있다. 격자판의 각 칸은 1 x 1 크기의 정사각형 모양이다. 당신은 이 격자판의 각 칸을 검은색 또는 흰색으로 칠할 계획이다.
- 당신은 격자판의 칸 중 몇 개(0개 이상 NM개 이하)는 검은색으로 칠할지 흰색으로 칠할지를 이미 정해 놓았다.
- 정확히 표현하자면, N X M 크기의 행렬 A가 있어서, Ai,j 가 ‘#’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해야 하고, Ai,j 가 ‘.’라면 격자판의 i행 j열에 있는 칸은 흰색으로 칠해야 하며, Ai,j 가 ‘?’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해도 되고 흰색으로 칠해도 된다.
- 당신은 아직 색이 정해지지 않은 칸들을 어떤 색으로 칠할지를 잘 정한 뒤 격자판을 색칠할 것이다.
- 색칠한 결과 격자판의 인접한 (즉, 변 하나를 공유하는) 두 칸의 색이 항상 다르게 할 수 있는지를 판단하는 프로그램을 작성하라.
[입력]
- 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
- 각 테스트 케이스의 첫 번째 줄에는 두 개의 자연수 N과 M(1 ≤ N ≤50, 1 ≤ M ≤ 50)이 공백 하나를 사이로 두고 주어진다.
- 다음 N개의 줄에는 ‘#’, ‘.’, ‘?’로만 구성된 길이가 M인 문자열이 하나씩 주어지며, 이는 행렬 A를 나타낸다.
[출력]
- 각 테스트 케이스마다, ‘?’에 해당하는 칸의 색을 잘 정하여, 격자판의 인접한 두 칸의 색이 항상 서로 다르게 할 수 있다면 ‘possible’을, 그렇지 않다면 ‘impossible’을 출력한다.
접근 방법
- BFS와 DFS 풀이 방법이 있다. DFS가 좀 더 문제에 접근하기 쉽고, BFS의 경우 조건처리가 까다롭다
- 코드 디버깅 에러 한 군데를 자꾸 못 찾아서 14번 도전 하고서야 찾음…
- 문제의 부분
// 잘못된 예 - BFS if (ch == '#') map[xx][yy] = '.'; else map[xx][yy] = '#'; // 이러면 물음표일 때도 #으로 바꿔버림
// 잘못된 예 - DFS
if (map[nx][ny] == '?') {
if (map[x][y] == '#') {
map[nx][ny] = '.';
dfs(nx, ny);
}
else if (map[nx][ny] == '.') { // x y 좌표에 접근해야 하는데 왜 nx ny에 접근하는가....
map[nx][ny] = '#';
dfs(nx, ny);
}
}
풀이 순서
- TC를 입력받아 해당 TC만큼 반복한다.
- N과 M을 입력받아 N M 크기만큼의 문자를 입력 받는다.
- BFS의 경우
- 입력 받을 때 물음표의 위치를 queue에 저장해둔다.
- 해당 큐 사이즈만큼 bfs 탐색을 돌며 격자판을 칠한다.
- 다 끝난 후 격자판을 체크하여 문제 조건에 맞으면 possible, 아니면 impossible을 출력한다.
- DFS의 경우
- 모든 입력을 받은 후, DFS 탐색을 한다.
- 다음 칸이 ?라면, 현재 칸이 #이냐 .이냐에 따라 반대되는 것으로 색칠하고, dfs탐색을 해당 nx ny로 한다.
- 다음 칸이 ?가 아니고, 지금 칸과 다음 칸의 값이 같다면, dfs 탐색을 종료하도록 한다.
- 탐색이 중간에 종료 됐다면, impossible을 출력하고, 아니라면 계속 탐색해 나간다.
소스코드
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int N, M;
char map[50][50];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
string answer = "possible";
void dfs(int x, int y) {
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (map[x][y] != '?' && map[x][y] == map[nx][ny]) {
answer = "impossible";
return;
}
if (map[nx][ny] == '?') {
if (map[x][y] == '#') {
map[nx][ny] = '.';
dfs(nx, ny);
}
else if (map[x][y] == '.') {
map[nx][ny] = '#';
dfs(nx, ny);
}
}
}
}
}
bool checkMap() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 현재 위치는 물음표가 아니여야 함
if (map[i][j] != '?') {
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (map[nx][ny] == '?') {
// 물음표면 넘어감
continue;
}
if (map[nx][ny] == map[i][j]) {
// 만약 같다면 바로 종료하도록 함.
return false;
}
}
}
}
}
}
return true;
}
int main() {
int TC;
cin >> TC;
for (int test_case = 1; test_case <= TC; test_case++) {
cin >> N >> M;
bool res = true;
queue<pair<int, int>> q;
// input
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
if (map[i][j] == '?')
q.push({ i, j });
}
}
// solution
while (!q.empty()) {
int xx = q.front().first;
int yy = q.front().second;
q.pop();
char ch = 'A'; // 초기값 세팅
for (int i = 0; i < 4; i++) {
int nx = xx + dx[i];
int ny = yy + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (ch == 'A') {
// 초기값이라면, 그 값에 해당 칸의 색 넣어줌
if (map[nx][ny] == '?') {
//물음표면 continue
continue;
}
else {
ch = map[nx][ny];
}
}
else {
if (map[nx][ny] != '?') {
if (ch != map[nx][ny]) {
// ch와 다음 맵의 색이 다름 -> 불가능해짐
res = false;
break;
}
}
}
}
}
if (!res)
break;
// 다른 색을 칠할 수 있으므로, 반대되는 색을 칠해줌
if (ch == '#')
map[xx][yy] = '.';
else if(ch == '.')
map[xx][yy] = '#';
}
/*
DFS 풀이
for (int i = 0; i < N; i++) {
if (answer == "impossible") {
break;
}
for (int j = 0; j < M; j++) {
if (answer == "impossible") {
break;
}
dfs(i, j);
}
}
cout << '#' << test_case << ' ' << answer << '\n';
answer = "possible";
*/
if (!res)
cout << "#" << test_case << " impossible\n";
else {
res = checkMap();
if (!res)
cout << "#" << test_case << " impossible\n";
else
cout << "#" << test_case << " possible\n";
}
}
return 0;
}
문제 풀이 결과
