[알고스팟/c++] 게임판 덮기 BOARDCOVER 문제 풀이

 

https://algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

 

접근 방식

---

1. 재귀함수로 게임판의 흰 칸을 가능한 블록 모양(네 가지)로 채우는 방식으로 풀면 되지 않을까? (가능한 모든 경우의 수를 세면서) 

재귀함수의 탈출 조건으로 게임판이 모두 '#'으로 채워져 있으면, 경우의 수를 1 추가해주고, 탈출하는 것으로 해준다.

 

2. 브루트포스로 모든 칸을 이중 for 문으로 돌면서, 흰 칸인 경우에, 네 가지 블록에 대해서 좌표 계산을 해서 블록을 놓을 수 있는 경우, '.'을 '#'으로 바꾸고, 재귀 호출로 새 게임판을 넘겨주어 같은 과정을 반복하도록 한다.

 

3. 블록은 세 칸으로 이루어졌으므로, 마지막 세 번째 칸을 확인하기 전까지는 일단 그 칸이 '.'이면 '#'으로 바꾸면서 확인해야 한다.

그래서 마지막 칸에서 실패하면 그 전에 바꾸어 주었던 칸을 다시 원래 상태로 되돌려주어야 한다.

 

4. 하지만 원래 상태로 되돌려줄 때, '#'이 원래부터 게임판에 있었던 검은 칸인지, 아니면 '.'을 바꾼 검은 칸인지 모른다.

그래서 해결 방법으로 떠오른 것이, '#'을 "처음으로" 만나서 블록을 놓을 수 없는 상태가 되었을 때, 그 전까지 '#'을 모두 '.'으로 바꾸어주는 것이다. 왜냐하면 처음으로 '#'을 만났다는 것은 그 전까지는 아직까지는 블록을 놓을 수 있다고 판단(블록 총 세 칸에 대해서 모두 게임판에 놓을 수 있어야 하기 때문에)한 것이기 때문이다. 

 

처음 문제에 접근한 방식이다.

하지만 이 접근 방식에는 크게 두 가지 오류가 있었다.

첫째는, 이 방식은 결과적으로 같은 방법으로 블록을 추가한 것인데 이를 "중복해서 세는 것"이 문제였다.

 

이는 왼쪽 상단에서부터 블록을 채워나가는 식으로 "순서를 강제적으로 고정시켜주어야 한다". 그렇기 때문에 "모든 칸을 이중 for 문으로 돌면서 재귀 호출을 하는 것"은 잘못된 방식이다. 이중 for 문을 도는 대신에 가장 처음 흰 칸을 만났을 때의 좌표 정보를 저장해서, 그 칸에 대해 네 가지 블록이 그려질 수 있는지 판단해야 한다. 

 

둘째로는, 블록의 좌표 정보를 저장하는 방식에 문제가 있었다.

int coverBlock[4][2][2] = {
	{{1,1},{0,1}},
	{{0,1},{1,1}},
	{{1,0},{1,1}},
	{{1,1},{1,0}}
};

/* 저장한 순서대로

1 1		<-- 기준이 인덱스 왼쪽 상단의 1이다.
0 1

0 1		<-- 기준이 인덱스 오른쪽 상단의 1이 된다. 모든 블록의 기준점은 왼쪽 상단의 1이어야 해야 한다.
1 1

1 0
1 1

1 1
1 0

*/

원래 이런 식으로 블록 정보를 저장했는데, 이는 블록에서 어떤 지점을 기준점으로 하는지가 애매해진다. 예를 들어, 첫 번째 모양은 현재 그 칸부터 바로 블록을 그리지만, 두 번째 모양의 경우 현재 그 칸은 0 이므로 그 오른쪽 옆에 칸에 블록을 추가하게 된다. 

 

따라서 모든 블록을 현재 칸을 기준점으로 잡도록 해야 한다. 

int coverBlock[4][3][2] = {
  {{0,0},{0,1},{1,1}},
  {{0,0},{1,0},{1,-1}},
  {{0,0},{1,0},{1,1}},
  {{0,0},{0,1},{1,0}}
};
/*

(1) 1
    1
  
   (1)
 1  1

(1)
 1  1

(1) 1
 1 

모든 블록의 세 칸의 좌표 정보는 괄호 좌표를 기준으로 하는 "상대적 좌표"가 저장된다.
*/

 

정답 코드

---

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 5e5;

int T, H, W, ans;
int board[20][20];
int coverBlock[4][3][2] = {
  {{0,0},{0,1},{1,1}},
  {{0,0},{1,0},{1,-1}},
  {{0,0},{1,0},{1,1}},
  {{0,0},{0,1},{1,0}}
};

bool check(int board[20][20], int y, int x, int typeBlock){
  for(int i = 0; i < 3; i++){
    int dY = y + coverBlock[typeBlock][i][0], dX = x + coverBlock[typeBlock][i][1];
    if(dY >= 0 && dY < H && dX >= 0 && dX < W){
      if(board[dY][dX] == 1){
        return false;
      }
    }
    else{
      return false;
    }
  }
  return true;
}

void solve(int board[20][20]){
  bool isBoardFull = true;
  pair <int,int> p = {-1,-1};
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(p.first == -1 && p.second == -1 && board[i][j] == 0){
        p.first = i;
        p.second = j;
        isBoardFull = false;
        break;
      }
    }
    if(!isBoardFull)
      break;
  }
  if(isBoardFull){
    ans++;
    return;
  }
  for(int k = 0; k < 4; k++){
    if(check(board,p.first,p.second,k)){
      for(int i = 0; i < 3; i++){
        int y = p.first + coverBlock[k][i][0], x = p.second + coverBlock[k][i][1];
        board[y][x] = 1;
      }
      solve(board);
      for(int i = 0; i < 3; i++){
        int y = p.first + coverBlock[k][i][0], x = p.second + coverBlock[k][i][1];
        board[y][x] = 0;
      }
    }
  }
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> T;
  while(T--){
    cin >> H >> W;
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        char c;
        cin >> c;
        board[i][j] = (c == '#') ? 1 : 0;
      }
    }
    solve(board);
    cout << ans << '\n';
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        board[i][j] = 0;
      }
    }
    ans = 0;
  }
  

	return 0;
}

"알고리즘 문제해결전략"에 있는 정해 코드는 훨씬 더 깔끔하고 간결하다.

앞으로 더 이해하기 쉽고 간결한 코드를 짜는 노력을 해야할 것 같다. (예를 들어, 함수의 기능 분리. 한 함수가 두 가지 기능을 하도록 설계하지 말자.)

 

배운 점

---

1. 블록에 대한 좌표 정보를 저장할 때는, 한 좌표를 기준삼아 나머지 칸들은 기준 칸에 대한 상대적 좌표를 저장하는 것이 어떨까?

2. 입력대로 검은 칸은 #으로, 흰 칸은 . 으로 저장하는 것보다, 처리하기 좋은 숫자값 1과 0으로 변환해서 저장하는 것도 방법이다. 숫자 연산으로 여러 가지 표현이 가능하기 때문이다.