예제: 게임판 덮기
문제
H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, . 는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.출력
한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.예제 입력(#이 안먹어서 H로 대신 쓴다!)
3 3 7 H.....H H.....H HH...HH 3 7 H.....H H.....H HH..HHH 8 10 HHHHHHHHHH H........H H........H H........H H........H H........H H........H HHHHHHHHHH예제 출력
0 2 1514
풀이
PICNIC 문제하고 비슷한 방식으로 풀었다.
map을 순회하며 빈 곳을 찾고, 순서대로 채워가는 방식이다.
다만 문제를 어렵게 만드는 것은 채울 수 있는 블럭이 4가지 방향으로 돌 수 있다는 것!
map을 벗어나도 안되고, 다른 블럭이랑 겹치지도 않아야하고, 벽 위에 둘 수도 없으니 이 예외들을 잘 처리해야겠다.
말은 이렇게 쉽게해도 필자도 삽질을 좀 했다😂
이런식의 문제(브루트포스, 다이나믹 프로그래밍 등등)들은 항상 예외처리 하기가 어려운것 같다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
using namespace std;
int H, W;
int map[20][20];
int dir[4][2][2] = {
{{0, 1}, {1, 0}},
{{0, 1}, {1, 1}},
{{1, 0}, {1, 1}},
{{1, -1}, {1, 0}},
};
int board() {
int y, x;
y = x = -1;
bool flag = false;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (map[i][j] == 0) {
y = i;
x = j;
flag = true;
break;
}
}
if (flag) break;
}
if (y == -1)
return 1;
int res = 0;
bool isChanged = false;
for (int i = 0; i < 4; i++) {
if (y + dir[i][0][0] >= 0 && x + dir[i][0][1] >= 0
&& y + dir[i][1][0] >= 0 && x + dir[i][1][1] >= 0
&& y + dir[i][0][0] < H && x + dir[i][0][1] < W
&& y + dir[i][1][0] < H && x + dir[i][1][1] < W
&& map[y + dir[i][0][0]][x + dir[i][0][1]] == 0
&& map[y + dir[i][1][0]][x + dir[i][1][1]] == 0) {
map[y][x] = 1;
map[y + dir[i][0][0]][x + dir[i][0][1]] = 1;
map[y + dir[i][1][0]][x + dir[i][1][1]] = 1;
res += board();
map[y][x] = 0;
map[y + dir[i][0][0]][x + dir[i][0][1]] = 0;
map[y + dir[i][1][0]][x + dir[i][1][1]] = 0;
isChanged = true;
}
}
if (!isChanged) return 0;
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
cin >> H >> W;
int blank = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
char ch;
cin >> ch;
// -1 : 벽, 0 : 빈공간, 1: 채워진거
if (ch == '#') map[i][j] = -1;
else if (ch == '.') {
map[i][j] = 0;
blank++;
}
else {
cerr << "입력이 잘못되었습니다." << endl;
return -1;
}
}
}
if (blank % 3 != 0) cout << 0 << endl;
else cout << board() << endl;
}
return 0;
}풀이 후기
항상 이런식의 문제는 꼭 삼성 기출문제 느낌이 난다. 난이도가 그정도라는 것은 아니고, 뭔가 조건등을 함수화하지 않으면 코드가 엄청나게 더러워보인다.
실제로, 필자가 썼던 어마어마한 if문
if (y + dir[i][0][0] >= 0 && x + dir[i][0][1] >= 0
&& y + dir[i][1][0] >= 0 && x + dir[i][1][1] >= 0
&& y + dir[i][0][0] < H && x + dir[i][0][1] < W
&& y + dir[i][1][0] < H && x + dir[i][1][1] < W
&& map[y + dir[i][0][0]][x + dir[i][0][1]] == 0
&& map[y + dir[i][1][0]][x + dir[i][1][1]] == 0)이거를 알고리즘 문제해결 전략 도서에서는 함수로 만들어버린다.
간단해진다고는 결코 말할 수 없지만, 보기에 훨씬 깔끔해진다.
코드도 요리처럼 보기좋은것이 더 좋은것이겠지. 유념하자.
