[알고리즘 문제 해결 전략] 06.5 문제: 게임판 덮기 (문제 ID: BOARDCOVER)

Daniel Oh·2023년 12월 4일

알고리즘 문제 해결 전략

목록 보기

4/7

1 문제

알고리즘 문제 해결 전략의 두번째 문제... 첫 문제 포스트를 정리하고 다시 풀기까지 많은 시간이 걸렸음... 문제를 푸는데 생각보다 엄청 헤맸다... 결국 이 블로그 글을 보고 깨달음을 얻음. 아래에 자세히 소개할 예정!

2 문제 해결 알고리즘

독해: 문제를 읽고 이해한다.

재정의+추상화: 문제를 익숙한 용어로 재정의한다.

설계: 어떻게 해결할지 계획을 세운다.

검증: 계획을 검증한다.

구현: 프로그램을 구현한다.

회고: 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

2-1 독해

게임판이 주어질 때 이 게임판을 3칸짜리 ㄴ자 블럭으로 모두 채우는 경우의 수를 구하는 문제이다.

"3칸짜리 ㄴ자 블럭": ㄴ자 블럭은 회전하여 ┌, ┐, ┘,└ 가 있다.

"경우의 수 구하기": 무식하게 풀기의 근간으로, 완전 탐색 (재귀 호출)이 떠오르는 대목이다.

2-2 재정의

게임판에 채울 수 있는 빈칸을 모두 ㄴ자 블럭으로 채운다. 독해 내용이 워낙 명확하여 굳이 추상화할 내용은 없는 것 같다.

2-3 설계

2-3-a 직관

일단... ㄴ자 블럭으로 채울 수 있는 빈칸이 있다면 넣고 재귀하고 빼고를 반복하면 될 것 같다.

2-3-b 체계적인 접근

2-3-b-1 비슷한 문제를 풀어본 적이 있나?

지난 문제 소풍에서 재귀 함수 작성법을 정리했다.

그때 정리했던 개수를 세는 재귀함수의 작성법은 다음과 같다.

// n : 전체 원소의 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 골라야할 원소의 수

void pick(int n, vector<int>& picked, int toPick){
	// 더 고를 원소가 없는 경우 원소들을 출력 또는 개수 세기
	if(toPick == 0) {
		printPicked(picked); 또는 cnt++;
		return;
	}
    
	// 고를 수 있는 원소들의 집합 순회하며 재귀함수 호출
	for(next = 원소 in 고를 수 있는 원소들의 집합) {
    	if (next가 조건을 충족함) {
            picked.push_back(next);
            pick(n, picked, toPick-1)
            picked.pop_back();
        }
	}
}

집합의 원소 하나하나를 고르거나 말거나 반복하며 결과를 만들어 출력하는, 개수를 세는 재귀 함수는 다음과 같은 과정을 거친다.
1. 기저 사례: 더 고를 원소가 없는 경우 결과를 출력하거나, 개수 증가 후 return
2. 고를 수 있는 원소들의 집합을 순회하며 넣고 -> 재귀 함수 호출 -> 빼고 반복

게임판 덮기 문제 역시 비슷하게 접근할 수 있을 것으로 보인다. 이런 느낌으로 말이다.

void cover() {
	if(게임판이 모두 덮였을 경우) {
		cnt++;
		return;
	}
    
	for(넣을 수 있는 위치 & ㄴ자 블록의 종류) {
    	if (해당 위치에 해당 블록을 넣을 수 있음) {
            boardCover(위치, 블록);
            cover();
            boardErasek(위치, 블록);
        }
	}
}

즉,
1. 위치를 순회하며 관찰 -> ㄴ자 블록을 넣을 수 있는 위치 찾기
2. 해당 위치에 넣을 수 있으면 넣고
3. 재귀함수 호출
4. 해당 위치에 넣었던 ㄴ자 블록을 빼고
5. 2~4를 모든 ㄴ자 블록을 넣을 수 있는 위치에 대하여 반복
하면 되지 않을까?

2-3-b-9 순서를 강제할 수 있나?

블럭을 채우는 경우의 수를 구하라고 했으니, 블럭을 채우는 순서는 고려하지 않아야 한다. 즉, 아래의 그림은 순서를 고려하면 채우는 경우의 수가 4가지이지만 순서를 고려하지 않으면 2가지이다.

즉, 블록을 채우는 순서는 주어지지 않았지만, 순서를 고려함으로써 정답에 더 가까워질 수 있다! 따라서 풀 때 이 점을 활용하면 괜찮은 접근인 것 같다. (하지만... 내가 문제를 풀 때 제대로 활용하지 못하여 문제를 틀리는 패인이 되었다 ㅠㅠ)

2-4 검증

재귀로 완전 탐색하는 방법

최악의 경우는 언제일까? 흰 칸의 개수가 최대인 상태일 것이다. 즉, 흰 칸이 50개가 있는 보드 게임판을 ㄴ자 블록으로 채우는 경우의 수이다. 이 때 채워야 하는 ㄴ자 블록은 50/3 ~= 17으로, 17개 정도가 나온다. 각 블록은 4가지 선택지를 가지므로, 4^17 = 2^34 = 2^7 * 2^27가지 이다. 즉, 약 128억 정도 연산하므로, 1억의 법칙에 의거해 128초 정도 걸릴 것이라고 예상할 수 있다. 그럼 문제를 못 푼다!

(앞서 말했듯이, 순서를 고려할 필요가 없으므로, 17!은 안 곱해주어도 된다.)

하지만 고려하지 않은 점이 한 가지 있다. 바로 한 블럭을 놓을 때마다 다른 블럭이 가질 수 있는 모양이 정해진다는 점이다. 따라서 경우의 수는 훨씬 줄어들을 것이다. (물론 구현을 빼놓고 해당 경우의 수가 충분히 줄어들었을지 검증하는 것은 증명하기 어렵다)

2-5 구현

재귀로 완전 탐색하는 방법 (FAILED)

이 코드는 처음에 작성했던 코드이다.

#include <bits/stdc++.h>
// #include "bits/stdc++.h"
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (uint)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

lld cnt = 0;
vector<vector<bool>> gameBoard;
int moveX[4] = {0, 1, 0, 1};
int moveY[4] = {0, 0, 1, 1};

int factorial(int n) {
  if (n == 1) return 1;
  return n * factorial(n - 1);
}

void printBoard() {
  for (int i = 0; i < sz(gameBoard); ++i) {
    string line;
    for (int j = 0; j < sz(gameBoard[0]); ++j) {
      if (gameBoard[i][j]) line += "W";
      else line += "B";
    }
    // cout << line << endl;
  }
}

bool isBoardAllCovered() {
    for (int i = 0; i < sz(gameBoard); ++i) {
        for (int j = 0; j < sz(gameBoard[0]); ++j) {
            if (gameBoard[i][j] == true) return false;
        }
    }
    return true;
}

bool isWhite(bool b) {
    return b;
}

int numOfWhiteIn2x2Board(int x, int y) {
    int num = 0;
    for (int i = 0; i < 4; ++i) {
        if (isWhite(gameBoard[x + moveX[i]][y + moveY[i]])) num++;
    }
    return num;
}

bool isBoardIncludeUnfillablePiece() {
    for (int i = 0; i < sz(gameBoard) - 1; ++i) {
        for (int j = 0; j < sz(gameBoard[0]) - 1; ++j) {
            if (numOfWhiteIn2x2Board(i, j) >= 3) return false;
        }
    }
    return true;
}

void fill2x2Board(int x, int y, int flag) {
    for (int i = 0; i < 4; ++i) {
        if (i != flag) gameBoard[x + moveX[i]][y + moveY[i]] = false;
    }
    return;
}

void erase2x2Board(int x, int y, int flag) {
    for (int i = 0; i < 4; ++i) {
        if (i != flag) gameBoard[x + moveX[i]][y + moveY[i]] = true;
    }
    return;
}

bool isRowAndColAllCovered(int x, int y) {
  for (int j = 0; j < sz(gameBoard); ++j) {
    for (int i = 0; i < sz(gameBoard[0]); ++i) {
      if (gameBoard[x][i] == true || gameBoard[j][y] == true) return false;
    }
  }
  return true;
}

bool isRowAllCovered(int x, int y) {
  for (int i = 0; i < sz(gameBoard[0]); ++i) {
    if (gameBoard[x][i] == true) return false;
  }
  return true;
}

bool isColAllCovered(int x, int y) {
  for (int j = 0; j < sz(gameBoard); ++j) {
    if (gameBoard[j][y] == true) return false;
  }
  return true;
}

void coverBoard(int x, int y) {
    // cout << "{" << endl;
    // printBoard();

    if ( isBoardAllCovered() ) {
      cnt++;
      // cout << "cnt = " << cnt << endl;
      // cout << "}" << endl;
      return;
    }
    
    if ( isBoardIncludeUnfillablePiece() ) {
      // cout << "Unfillable" << endl;
      // cout << "}" << endl;
      return;
    }
    
    if ( isRowAllCovered(x, y) ) {
      coverBoard(x + 1, y);
      return;
    }
    
    if ( isColAllCovered(x, y) ) {
      coverBoard(x, y + 1);
      return;
    }
    
    for (int i = x; i < sz(gameBoard) - 1; ++i) {
      for (int j = y; j < sz(gameBoard[0]) - 1; ++j) {
        if (numOfWhiteIn2x2Board(i, j) == 4) {
            for (int k = 3; k >= 0; --k) {
                fill2x2Board(i, j, k);
                coverBoard(x, y);
                erase2x2Board(i, j, k);
                // printBoard();
            }
        } else if (numOfWhiteIn2x2Board(i, j) == 3) {
            if (!isWhite(gameBoard[i][j])) {
                fill2x2Board(i, j, 0);
                coverBoard(x, y);
                erase2x2Board(i, j, 0);
                // printBoard();
            } else if (!isWhite(gameBoard[i + 1][j])) {
                fill2x2Board(i, j, 1);
                coverBoard(x, y);
                erase2x2Board(i, j, 1);
                // printBoard();
            } else if (!isWhite(gameBoard[i][j + 1])) {
                fill2x2Board(i, j, 2);
                coverBoard(x, y);
                erase2x2Board(i, j, 2);
                // printBoard();
            }
            else if (!isWhite(gameBoard[i + 1][j + 1])) {
                fill2x2Board(i, j, 3);
                coverBoard(x, y);
                erase2x2Board(i, j, 3);
                // printBoard();
            }
        }
      }
    }

    // cout << "}" << endl;
    return ;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int c;
    cin >> c;

    for (int i = 0; i < c; ++i) {
        int h, w;
        cin >> h >> w;
        gameBoard.resize(h);
        for (int j = 0; j < h; ++j) {
            gameBoard[j].resize(w);
        }
        int numOfWhite = 0;
        for (int j = 0; j < h; ++j) {
            string line;
            cin >> line;
            for (int k = 0; k < w; ++k) {
                gameBoard[j][k] = (line[k] == '.') ? true : false;
                if (line[k] == '.') numOfWhite++;
            }
        }

        cnt = 0;
        coverBoard(0, 0);
        cout << cnt / factorial(numOfWhite / 3) << endl;
    }

    return 0;
}

이 코드는... 약 5시간 동안 구현한 코드이다...

base case

만약 보드가 다 덮여지면 cnt를 증가시키고 return한다.
만약 덮을 수 있는 조각이 없다면 return한다.

recursive case

한 줄이 다 찼다면 한 줄 아래에서 돈다.
한 열이 다 찼다면 한 열 옆에서 돈다.
해당 구역을 2중 for loop로 돌면서 2x2 크기의 박스로 관찰한다.
3-1. 만약 4칸 모두 비어있다면 ┌, ┐, ┘,└ 를 모두 시도한다.
3-2. 만약 3칸만 비어있다면 해당 3칸을 모두 채워 ㄴ자 블록 채우기를 시도한다.

변곡점: 순서를 고려해버림 문제

cout문들을 주석 해제하여 내용을 분석해보자.

입력

1
4 3
..#
..#
..#
###

출력

{
WWB
WWB
WWB
BBB
{
BBB
BWB
WWB
BBB
{
BBB
BWB
WWB
BBB
{
BBB
BBB
BBB
BBB
cnt = 1
}
BBB
BWB
WWB
BBB
}
WWB
WWB
WWB
BBB
{
BWB
BBB
WWB
BBB
Unfillable
}
WWB
WWB
WWB
BBB
{
BBB
WBB
WWB
BBB
{
BBB
WBB
WWB
BBB
{
BBB
BBB
BBB
BBB
cnt = 2
}
BBB
WBB
WWB
BBB
}
WWB
WWB
WWB
BBB
{
WBB
BBB
WWB
BBB
Unfillable
}
WWB
WWB
WWB
BBB
{
WWB
BBB
BWB
BBB
Unfillable
}
WWB
WWB
WWB
BBB
{
WWB
BWB
BBB
BBB
{
BBB
BBB
BBB
BBB
cnt = 3
}
WWB
BWB
BBB
BBB
}
WWB
WWB
WWB
BBB
{
WWB
BBB
WBB
BBB
Unfillable
}
WWB
WWB
WWB
BBB
{
WWB
WBB
BBB
BBB
{
BBB
BBB
BBB
BBB
cnt = 4
}
WWB
WBB
BBB
BBB
}
WWB
WWB
WWB
BBB
}
2

cnt는 4로, 순서를 고려하여 채우는 모든 경우의 수를 셈을 확인할 수 있다. 따라서, ㄴ자 블록을 배열할 수 있는 경우의 수인 factorial(numOfWhite / 3)로 나눠주면, 올바른 정답을 출력해낸다. (허나, 이것은 오버플로우 내지는 시간 초과를 야기할 수 있을 것이다.)

결과

결과는... 예상했듯이 시간 초과.

결국 순서를 고려하는 다른 방법이 필요하다!

재귀로 완전 탐색하는 방법 (REFERENCE)

도무지 해결을 못하겠어서 설명이 잘 되어있는 블로그 글을 참고하여 코드를 작성하였다.

#include <bits/stdc++.h>
// #include "bits/stdc++.h"
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (uint)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

int cnt = 0;
vector<vector<bool>> board;

const pii LTYPES[4][3] = {
  { make_pair(0,0), make_pair(0,1), make_pair(1,0) },
  { make_pair(0,0), make_pair(0,1), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,-1) },
};

bool isWhite(bool b) {
    return b;
}

void printBoard() {
  for (int i = 0; i < sz(board); ++i) {
    string line;
    for (int j = 0; j < sz(board[0]); ++j) {
      if (isWhite(board[i][j])) line += "W";
      else line += "B";
    }
    cout << line << endl;
  }
}

pii findWhite() {
  for (int i = 0; i < sz(board); ++i) {
    for (int j = 0; j < sz(board[0]); ++j) {
      if (isWhite(board[i][j])) return make_pair(i, j);
    }
  }
  return make_pair(-1, -1);
}

bool isLInBoard(int x, int y) {
  return 0 <= x && x < sz(board) && 0 <= y && y < sz(board[0]);
}

bool isLPlacable (int x, int y, int state) {
  for (int i = 0; i < 3; ++i) {
    int nx = x + LTYPES[state][i].first;
    int ny = y + LTYPES[state][i].second;
    // cout << nx << " " << ny << endl;
    if (!isLInBoard(nx, ny) || !isWhite(board[nx][ny])) return false;
  }
  return true;
}

void coverLInBoard(int x, int y, int state, char c) {
  for (auto move : LTYPES[state]) {
    int nx = x + move.first;
    int ny = y + move.second;
    if (c == 'W') board[nx][ny] = true;
    else if (c == 'B') board[nx][ny] = false;
  }
}

void solve() {
  // cout << "{" << endl;
  // printBoard();

  int whiteX = findWhite().first;
  int whiteY = findWhite().second;

  // cout << whiteX << " " << whiteY << endl;

  if (whiteX == -1) {
    cnt++;
    // cout << "cnt = " << cnt << endl;
    // cout << "}" << endl;
    return;
  }

  for (int s = 0; s < 4; ++s) {
    if (isLPlacable(whiteX, whiteY, s)) {
      coverLInBoard(whiteX, whiteY, s, 'B');
      solve();
      coverLInBoard(whiteX, whiteY, s, 'W');
      // printBoard();
    }
  }
  // cout << "}" << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int c;
    cin >> c;

    while (c--) {
        int h, w;
        cin >> h >> w;
        board.resize(h);
        for (int j = 0; j < h; ++j) {
            board[j].resize(w);
        }
        int numOfWhite = 0;
        for (int j = 0; j < h; ++j) {
            string line;
            cin >> line;
            for (int k = 0; k < w; ++k) {
                board[j][k] = (line[k] == '.') ? true : false;
                if (line[k] == '.') numOfWhite++;
            }
        }

        cnt = 0;
        solve();
        cout << cnt << endl;
        
        // cout << LTYPES[0][0].first << " " << LTYPES[0][0].second << endl;
        // cout << LTYPES[0][1].first << " " << LTYPES[0][1].second << endl;
        // cout << LTYPES[0][2].first << " " << LTYPES[0][2].second << endl;
        // cout << LTYPES[1] << endl;
        // cout << LTYPES[2] << endl;
        // cout << LTYPES[3] << endl;
    }

    return 0;
}

코드가 훨씬 간결하다!

좋은 코드를 작성하기 위한 원칙 적용

간결한 코드 작성: 답을 내기 위한 cnt와 board를 글로벌 변수로 정의했다. (한 가지 아쉬운 점은, ㄴ자 블록 데이터를 접근할 때 인덱스로 접근했다는 점이다. 범위 기반 반복문을 사용하면 더 간결하게 작성할 수 있었을 것 같다.) 또 coverLInBoard() 함수는 c 값에 따라 보드판을 'W'로 채우거나 'B'로 채울 수 있게 설계하였다. 같은 기능을 하는 함수를 두 개 만들지 않기 위한 방법이다.
적극적으로 코드 재사용: 함수를 적극적으로 쪼개며 만들었다. 단 isWhite() 함수는 굳이 싶기도 하다. 차라리 board를 isBoardWhite 이런 식으로 정의했으면 애시당초 isWhite()를 만들 필요가 없지 않았을까?
표준 라이브러리 공부: std::vector와 std::pair를 적극적으로 사용했다.
항상 같은 형태로 프로그램 작성: 지난 소풍 문제와 거의 일관된 방식으로 코드를 작성하였다.
일관적이고 명료한 명명법 사용: 함수 이름, 변수 이름에 공들였다. 단 앞서 언급했듯 isWhite() 함수는 굳이 싶기도 하다.
모든 자료를 정규화하여 저장: 딱히 사용된 지점이 없는 것 같다.
코드와 데이터 분리: ㄴ자 블록 데이터를 작성할 때 다음과 같이 데이터를 따로 작성하였다.

const pii LTYPES[4][3] = {
  { make_pair(0,0), make_pair(0,1), make_pair(1,0) },
  { make_pair(0,0), make_pair(0,1), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,-1) },
};

채점 결과

결과는... 성공!

업로드중..

그것도 0ms 성공 ㄷㄷ

내 코드와의 차이점은

ㄴ자 블록을 넣을 수 있는 위치를 탐색할 때 2x2 단위로 관찰하지 않고 1x1, 즉 한 칸 단위로 관찰한다.
ㄴ자 블록을 넣을 수 있는 위치를 탐색하는 함수를 따로 만들어 재귀에 포함되지 않도록 한다.

2번 내용은 매우 중요하다! 결국 내가 이 문제를 해결하지 못했던 결정적인 요인은 재귀되는 함수 내에서 과도하게 반복문을 사용했기 때문이다. 넣을 수 있는 위치를 탐색하기 위해서라면, 그냥 탐색하는 함수를 재귀 함수 밖으로 빼내서 따로 처리하면 된다.

한 번 이 내용을 바탕으로 내 코드를 고쳐볼까?

재귀로 완전 탐색하는 방법 (FIXED - FAILED)

#include <bits/stdc++.h>
// #include "bits/stdc++.h"
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (uint)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

lld cnt = 0;
vector<vector<bool>> gameBoard;
int moveX[4] = {0, 1, 0, 1};
int moveY[4] = {0, 0, 1, 1};

void printBoard() {
  for (int i = 0; i < sz(gameBoard); ++i) {
    string line;
    for (int j = 0; j < sz(gameBoard[0]); ++j) {
      if (gameBoard[i][j]) line += "W";
      else line += "B";
    }
    cout << line << endl;
  }
}

bool isBoardAllCovered() {
    for (int i = 0; i < sz(gameBoard); ++i) {
        for (int j = 0; j < sz(gameBoard[0]); ++j) {
            if (gameBoard[i][j] == true) return false;
        }
    }
    return true;
}

bool isWhite(bool b) {
    return b;
}

int numOfWhiteIn2x2Board(int x, int y) {
    int num = 0;
    for (int i = 0; i < 4; ++i) {
        if (isWhite(gameBoard[x + moveX[i]][y + moveY[i]])) num++;
    }
    return num;
}

bool isBoardIncludeUnfillablePiece() {
    for (int i = 0; i < sz(gameBoard) - 1; ++i) {
        for (int j = 0; j < sz(gameBoard[0]) - 1; ++j) {
            if (numOfWhiteIn2x2Board(i, j) >= 3) return false;
        }
    }
    return true;
}

void fill2x2Board(int x, int y, int flag) {
    for (int i = 0; i < 4; ++i) {
        if (i != flag) gameBoard[x + moveX[i]][y + moveY[i]] = false;
    }
    return;
}

void erase2x2Board(int x, int y, int flag) {
    for (int i = 0; i < 4; ++i) {
        if (i != flag) gameBoard[x + moveX[i]][y + moveY[i]] = true;
    }
    return;
}

pii findLFillable() {
  for (int i = 0; i < sz(gameBoard) - 1; ++i) {
    for (int j = 0; j < sz(gameBoard[0]) - 1; ++j) {
      if (numOfWhiteIn2x2Board(i, j) == 4 || numOfWhiteIn2x2Board(i, j) == 3) {
        return make_pair(i, j);
      }
    }
  }
  return make_pair(-1, -1);
}

void coverBoard() {
    // cout << "{" << endl;
    // printBoard();

    if ( isBoardAllCovered() ) {
      cnt++;
      // cout << "cnt = " << cnt << endl;
      // cout << "}" << endl;
      return;
    }
    
    if ( isBoardIncludeUnfillablePiece() ) {
      // cout << "Unfillable" << endl;
      // cout << "}" << endl;
      return;
    }
    
    int i = findLFillable().first;
    int j = findLFillable().second;
    
    if (numOfWhiteIn2x2Board(i, j) == 4) {
        for (int k = 3; k >= 0; --k) {
            fill2x2Board(i, j, k);
            coverBoard();
            erase2x2Board(i, j, k);
            // printBoard();
        }
    } else if (numOfWhiteIn2x2Board(i, j) == 3) {
        if (!isWhite(gameBoard[i][j])) {
            fill2x2Board(i, j, 0);
            coverBoard();
            erase2x2Board(i, j, 0);
            // printBoard();
        } else if (!isWhite(gameBoard[i + 1][j])) {
            fill2x2Board(i, j, 1);
            coverBoard();
            erase2x2Board(i, j, 1);
            // printBoard();
        } else if (!isWhite(gameBoard[i][j + 1])) {
            fill2x2Board(i, j, 2);
            coverBoard();
            erase2x2Board(i, j, 2);
            // printBoard();
        }
        else if (!isWhite(gameBoard[i + 1][j + 1])) {
            fill2x2Board(i, j, 3);
            coverBoard();
            erase2x2Board(i, j, 3);
            // printBoard();
        }
    }

    // cout << "}" << endl;
    return ;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int c;
    cin >> c;

    for (int i = 0; i < c; ++i) {
        int h, w;
        cin >> h >> w;
        gameBoard.resize(h);
        for (int j = 0; j < h; ++j) {
            gameBoard[j].resize(w);
        }
        int numOfWhite = 0;
        for (int j = 0; j < h; ++j) {
            string line;
            cin >> line;
            for (int k = 0; k < w; ++k) {
                gameBoard[j][k] = (line[k] == '.') ? true : false;
            }
        }

        cnt = 0;
        coverBoard();
        cout << cnt << endl;
    }

    return 0;
}

해당 코드는 ㄴ자 블록을 넣을 수 있는 위치를 반환하는 함수를 재귀로부터 떼내어 작성한 코드이다.

pii findLFillable() {
  for (int i = 0; i < sz(gameBoard) - 1; ++i) {
    for (int j = 0; j < sz(gameBoard[0]) - 1; ++j) {
      if (numOfWhiteIn2x2Board(i, j) == 4 || numOfWhiteIn2x2Board(i, j) == 3) {
        return make_pair(i, j);
      }
    }
  }
  return make_pair(-1, -1);
}

변곡점: 3칸이 비었을 때 3칸을 채워버리면 안됨 문제

허허허... 근간이 잘못되었음을 깨달았다. 3칸이 비워져있을 때 3칸을 시도해버리면 안된다. (정확하게는, 3칸만 넣는 것을 시도하면 안된다.)

입력1

1
4 3
..#
..#
..#
###

출력1

{
WWB
WWB
WWB
BBB
{
BBB
BWB
WWB
BBB
{
BBB
BBB
BBB
BBB
cnt = 1
}
BBB
BWB
WWB
BBB
}
WWB
WWB
WWB
BBB
{
BWB
BBB
WWB
BBB
Unfillable
}
WWB
WWB
WWB
BBB
{
BBB
WBB
WWB
BBB
{
BBB
BBB
BBB
BBB
cnt = 2
}
BBB
WBB
WWB
BBB
}
WWB
WWB
WWB
BBB
{
WBB
BBB
WWB
BBB
Unfillable
}
WWB
WWB
WWB
BBB
}
2

훌륭하게 잘 동작한다! 이제 중복으로 세는 문제를 해결한 줄 알았건만...

입력2

1
3 7 
#.....# 
#.....# 
##..###

출력2

{
BWWWWWB
BWWWWWB
BBWWBBB
{
BBBWWWB
BBWWWWB
BBWWBBB
{
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBBBB
BBBBBWB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBBWB
BBBBBBB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBBBB
BBBBWBB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBWBB
BBBBBBB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
}
BBBWWWB
BBWWWWB
BBWWBBB
}
BWWWWWB
BWWWWWB
BBWWBBB
{
BBWWWWB
BBBWWWB
BBWWBBB
{
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBBBB
BBBBBWB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBBWB
BBBBBBB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBBBB
BBBBWBB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
{
BBBBWBB
BBBBBBB
BBWWBBB
Unfillable
}
BBBBWWB
BBBBWWB
BBWWBBB
}
BBWWWWB
BBBWWWB
BBWWBBB
}
BWWWWWB
BWWWWWB
BBWWBBB
{
BBBWWWB
BWBWWWB
BBWWBBB
{
BBBBBWB
BWBBWWB
BBWWBBB
{
BBBBBBB
BWBBBBB
BBWWBBB
Unfillable
}
BBBBBWB
BWBBWWB
BBWWBBB
}
BBBWWWB
BWBWWWB
BBWWBBB
{
BBBBWWB
BWBBBWB
BBWWBBB
{
BBBBBBB
BWBBBBB
BBWWBBB
Unfillable
}
BBBBWWB
BWBBBWB
BBWWBBB
}
BBBWWWB
BWBWWWB
BBWWBBB
{
BBBBBWB
BWBWBWB
BBWWBBB
{
BBBBBWB
BWBBBWB
BBBBBBB
Unfillable
}
BBBBBWB
BWBWBWB
BBWWBBB
}
BBBWWWB
BWBWWWB
BBWWBBB
{
BBBWBWB
BWBBBWB
BBWWBBB
Unfillable
}
BBBWWWB
BWBWWWB
BBWWBBB
}
BWWWWWB
BWWWWWB
BBWWBBB
{
BWBWWWB
BBBWWWB
BBWWBBB
{
BWBBBWB
BBBBWWB
BBWWBBB
{
BWBBBBB
BBBBBBB
BBWWBBB
Unfillable
}
BWBBBWB
BBBBWWB
BBWWBBB
}
BWBWWWB
BBBWWWB
BBWWBBB
{
BWBBWWB
BBBBBWB
BBWWBBB
{
BWBBBBB
BBBBBBB
BBWWBBB
Unfillable
}
BWBBWWB
BBBBBWB
BBWWBBB
}
BWBWWWB
BBBWWWB
BBWWBBB
{
BWBBBWB
BBBWBWB
BBWWBBB
{
BWBBBWB
BBBBBWB
BBBBBBB
Unfillable
}
BWBBBWB
BBBWBWB
BBWWBBB
}
BWBWWWB
BBBWWWB
BBWWBBB
{
BWBWBWB
BBBBBWB
BBWWBBB
Unfillable
}
BWBWWWB
BBBWWWB
BBWWBBB
}
BWWWWWB
BWWWWWB
BBWWBBB
}
0

허허허... 문제를 찾았는가? 문제는 바로

BBBWWWB
BBWWWWB
BBWWBBB
...
BBBBWWB
BBBBWWB
BBWWBBB

이 구간에 있다. 두 번째 블럭을 넣어버리는 순간, 이 보드판은 절대로 채워질 수 없다. 그럼 정답인 경우는? 바로 두 번째 블럭이 이렇게 채워져야 한다.

BBBWWWB
BBWWWWB
BBWWBBB
...
BBBBBWB
BBWBWWB
BBWWBBB
or
BBBBWWB
BBWBBWB
BBWWBBB

이렇게 채워져야 후일을 도모할 수 있다.

허나 내가 짠 코드는 2x2 구간 내에 3칸이 비어있으면 바로 3칸을 넣어버린다... 이는 구현 단계에서 모든 케이스를 꼼꼼히 보지 못한 실수이다.

따라서, 두번째 구현이 가장 훌륭해보인다. 2x2 구간으로 관찰하지 않음으로써, 코드가 매우 정갈해졌다.

2-6 회고

2-6-1 입력: 테스트 케이스 개수가 주어질 때

테스트 케이스 개수(c)가 주어질 때, 여태까지 for문을 사용하여 해결했다. 하지만 while문을 사용하면 더 멋있게 처리할 수 있다.

before (for)

int main()
{
    uint c;
    cin >> c;

    for (int i = 0; i < c; ++i) {
        테스트 케이스에 대한 입력
        입력 처리
        테스트 케이스에 대한 출력
    }

    return 0;
}

after (while)

int main()
{
    uint c;
    cin >> c;

    while (c--) {
        테스트 케이스에 대한 입력
        입력 처리
        테스트 케이스에 대한 출력
    }

    return 0;
}

테스트 케이스 입력은 while문으로 간결하게 처리하자.

2-6-2 `char` vs `string`

string은 char의 배열이다. 따라서 문자열이 아닌 문자를 비교하기 위해서는 "x"가 아닌 'x'를 사용해야 한다.

문자열(string)과 문자(char)를 엄격히 구분하여 "x"와 'x'를 사용하자.

필자는 입력받을 때 == '.'을 == "."으로 작성하여 틀렸다.

2-6-3 `Array` 초기화 vs `Vector` 초기화

ㄴ자 모양 블럭의 종류를 정의할 때, 다음과 같은 코드를 사용했다.

const pii LTYPES[4][3] = {
  { make_pair(0,0), make_pair(0,1), make_pair(1,0) },
  { make_pair(0,0), make_pair(0,1), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,-1) },
};

이는 배열을 특정 값으로 미리 세팅한 것이다. 이에 대한 문법을 정리해보고자 한다.

`Array` 초기화

Array 초기화에 대한 cppreference

배열을 특정 값으로 초기화하고 싶다면 다음과 같이 작성하면 된다.

{elem_type} {name}[{size}] = { elem1, elem2, ..., elemn}

`Vector` 초기화

Vector 초기화에 대한 GeeksForGeeks

배열을 특정 값으로 초기화하고 싶다면 다음과 같이 작성하면 된다.

vector<{elem_type}> {name}{ elem1, elem2, ..., elemn}

따라서 만약 ㄴ자 블록을 벡터로 정의하고 했다면, 다음과 같이 작성할 수 있다.

const vector<vector<pii>> LTYPES {
  { make_pair(0,0), make_pair(0,1), make_pair(1,0) },
  { make_pair(0,0), make_pair(0,1), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,-1) },
};

구르미 님의 Vector 초기화 방식

구르미 님은 ㄴ자 모양 블럭의 종류를 정의할 때, 다음과 같은 코드를 작성했다.

const vector<pair<int, int>> TYPES[4] = {
    { make_pair(0, 0), make_pair(1, 0), make_pair(0, 1) },  
    { make_pair(0, 0), make_pair(1, 0), make_pair(1, 1) },  
    { make_pair(0, 0), make_pair(0, 1), make_pair(1, 1) }, 
    { make_pair(0, 0), make_pair(0, 1), make_pair(-1, 1) }  
};

이게 도대체 무슨 말일까?!? 곰곰히 고민하다가 벡터를 원소로 가지는 배열임을 깨달았다.

이 방식이 배열을 초기화하는 방식보다 가지는 이점이 무엇일까? 나는 범위 기반 반복문(Range-based for loop)의 사용이 가능하다는 점이라고 생각했다.

범위 기반 반복문에 대한 설명

만약 배열을 사용하여 해당 데이터를 순회한다면?

const pair<int, int> TYPES_ARR_ARR[4][3] = {
  { make_pair(0,0), make_pair(0,1), make_pair(1,0) },
  { make_pair(0,0), make_pair(0,1), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,1) },
  { make_pair(0,0), make_pair(1,0), make_pair(1,-1) },
};

...

for (int i = 0; x < 4; ++i) {
   for (int j = 0; j < 3; ++j) {
   	   cout << LTYPES_ARR_ARR[i][j].first << " " << LTYPES_ARR_ARR[i][j].second << endl;
   }
   cout << endl;
}

만약 구르미 님의 방식으로 해당 데이터를 순회한다면?

const vector<pair<int, int>> TYPES_ARR_VEC[4] = {
    { make_pair(0, 0), make_pair(1, 0), make_pair(0, 1) },  
    { make_pair(0, 0), make_pair(1, 0), make_pair(1, 1) },  
    { make_pair(0, 0), make_pair(0, 1), make_pair(1, 1) }, 
    { make_pair(0, 0), make_pair(0, 1), make_pair(-1, 1) }  
};

...

for (int i = 0; i < 4; ++i) {
  	for (auto move : LTYPES_ARR_VEC[i]) {
    	cout << move.first << " " << move.second << endl;
  	}
  	cout << endl;
}

훨씬 깔끔한 방식으로 코드를 작성할 수 있다!

배열 초기화 방법:
{elem_type} {name}[{size}] = { elem1, elem2, ..., elemn}
벡터 초기화 방법:
vector<{elem_type}> {name}{ elem1, elem2, ..., elemn}
배열과 백터를 적절히 조합하고, 범위 기반 반복문을 활용해 반복문 코드를 더 간결하게 작성할 수 있다!

2-6-4 보드판을 탐색하는 상황

보드판을 순회하며 탐색하는 상황에서는 2x2 블럭 단위로 접근하며 순회하면 안되고, 1x1 단위로 접근하는게 좋아보인다. 2x2 블럭 단위로 접근하게 되면 생각해야 하는 경우의 수가 늘어난다. 예를 들어, 내가 구현했던 코드는 2x2 블럭 단위로 탐색하기 때문에 3칸이 존재할 때 무조건 채우고 시작한다는 문제가 있다. 이는 1x1 단위로 접근하지 않으면 해결하지 못할 것으로 보인다.

보드판을 순회하며 탐색하는 상황에서는 2x2 블럭 단위로 접근하며 순회하지 말고, 1x1 단위로 접근하자.

3 구종만's Sol

3-1 구종만's 설계

링크텍스트

흰 칸의 수를 3으로 나눠서 내려 놓을 블록의 수 N을 얻은 뒤, 문제의 답을 생성하는 과정을 N조각으로 나눠 한 조각에서 한 블록을 내려놓도록 하자. 재귀 함수는 주어진 게임판에 블록을 한 개 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하면 될 것이다.

3-2 구종만's 검증 (중복으로 세는 문제)

허나, 이런 방식으로는 덮을 수 있는 방법의 수를 셀 수 없다. 블록을 놓는 순서는 이 문제에서 전혀 중요하지 않은데, 방금 설계는 같은 배치도 블록을 놓는 순서에 따라서 여러 번 세기 때문이다.

해결 방법 using 정규화

가장 간단한 해결 방법은 재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하는 것이다. (즉, 빈 칸을 채울 ㄴ자 블록의 순서를 강제하는 것이다.) 이렇게 하면 한 답을 한 가지 방법으로 밖에 생성할 수 없으므로 중복으로 세는 문제를 해결할 수 있다.

3-3 구종만's 검증 (답의 수의 상한)

최악의 경우는 흰 칸의 개수가 최대인 상태일 것이다. 즉, 흰 칸이 50개가 있는 보드 게임판을 ㄴ자 블록으로 채우는 경우의 수이다. 이 때 채워야 하는 ㄴ자 블록은 50/3 ~= 16이기 때문에 답의 상한은 4^16 = 2^32 = 2^5 * 2^27가지 이다. 즉, 약 32억 정도 연산하므로, 1억의 법칙에 의거해 32초 정도 걸릴 것이라고 예상할 수 있다. 그럼 문제를 못 푼다!

하지만 실제 입력을 손으로 풀어 보면 각 단계에서 우리가 선택할 수 있는 블록 배치가 크게 제한됨을 알 수 있다. 흰 칸이 48개 있는 세 번째 예제 입력의 답은 4^16 = 2^32가지가 나올 것으로 계산되지만, 실상은 1514 밖에 되지 않음을 보더라도 실제 답의 수는 이 상한보다 훨씬 작으리라고 예측할 수 있다.

3-4 구종만's 구현

#include <iostream>

using namespace std;

const int coverType[4][3][2] = {
    {{0, 0}, {1, 0}, {0, 1}}, //┌─
    {{0, 0}, {0, 1}, {1, 1}}, // ─┐
    {{0, 0}, {1, 0}, {1, 1}}, // └─
    {{0, 0}, {1, 0}, {1, -1}} // ─┘
};

// y,x,위치에서 type 도형(┌─,─┐,└─,─┘)을 놓을 수 있는지 검사
// delta가 1이면 덮고, -1이면 덮었던 블록을 없앤다.
bool set(int y, int x, int type, int delta) 
{
    bool ok = true;
    for (int i = 0; i < 3; i++)
    {
        const int ny = y + coverType[type][i][0];
        const int nx = x + coverType[type][i][1];

        if (ny < 0 || ny >= height || nx < 0 || nx >= width)
        {
            ok = false;
        }
        else if ((map[ny][nx] += delta) > 1)
        {
            ok = false;
        }
    }
    return ok;
}

int cover()
{
    int y = -1, x = -1;

    for (int h = 0; h < height; h++)
    {
        for (int w = 0; w < width; w++)
        {
            if (map[h][w] == 0)
            {
                x = w;
                y = h;
                break;
            }
        }
        if (y != -1)
        {
            break;
        }
    }
    
    // base case: 모든 칸을 채웠으면 1을 반환
    if (y == -1)
    {
        return 1;
    }

    int count = 0;
    for (int type = 0; type < 4; type++)
    {

        if (set(y, x, type, 1)) // 블록을 덮어본다.
        {
            count += cover(); // 덮어진다면 재귀 함수의 반환값을 더한다.
        }
        set(y, x, type, -1); // 덮었던 블록을 다시 지운다.
    }

    return count;
}

3-5 구종만's Sol을 읽고 또 회고

3-5-1 코드 재사용성 (함수 쪼개기)

솔직히 종만 씨 코드보다 내가 작성한 코드가 더 나은 것같다. 나는

ㄴ자 블록을 넣는 위치를 찾는 함수 findWhite()
점의 좌표가 보드판 내에 있는지 판별하는 함수 isLInBoard()
주어진 ㄴ자 블록을 보드판 내 주어진 위치에 위치시킬 수 있는지 판별하는 함수 isLPlacable

허나 종만 씨의 코드는 위와 같이 함수를 쪼개지 않고 대부분 함수 안에 직접 작성했다. 물론 코드의 길이를 줄일 수 있다는 이점이 있으나, 코드에 대한 설명이 부족해 다시 볼 때 이해에 시간이 더 걸릴 것 같다는 생각이 든다.

3-5-2 표준 라이브러리의 사용

내 코드는 std::pair<int, int>를 적극적으로 활용하여 순서쌍 좌표를 멋지게 표현하려고 노력했다. 허나 종만 씨의 코드는 pair를 사용하지 않았을 뿐만 아니라, x와 y가 무엇인지, pair와 어떤 대응 관계를 이루는 지 서술하지 못했다. 따라서... 약간 아쉽다.

3-5-3 개수를 세는 재귀 함수 (`void` 재귀 말고 `int` 재귀 해보기)

지난 소풍 문제에서 개수를 세는 재귀 함수의 스켈레톤 코드를 작성한 적이 있다.

// n : 전체 원소의 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 골라야할 원소의 수

int cnt = 0;

void pick(int n, vector<int>& picked, int toPick){
	// 더 고를 원소가 없는 경우 개수 세기
	if(toPick == 0) {
		cnt++;
		return;
	}
    
	// 고를 수 있는 원소들의 집합 순회하며 재귀함수 호출
	for(next = 원소 in 고를 수 있는 원소들의 집합) {
    	if (next가 조건을 충족함) {
            picked.push_back(next);
            pick(n, picked, toPick-1)
            picked.pop_back();
        }
	}
}

이는 void 함수를 재귀하는 형태이다. 이를 int 함수를 재귀하는 형태로 바꾸면 다음과 같다.

// n : 전체 원소의 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 골라야할 원소의 수

int pick(int n, vector<int>& picked, int toPick){
	// 결과값
    int cnt = 0;
    
    // 더 고를 원소가 없는 경우 1 반환
	if(toPick == 0) return 1;
    
	// 고를 수 있는 원소들의 집합 순회하며 재귀함수 호출
	for(next = 원소 in 고를 수 있는 원소들의 집합) {
    	if (next가 조건을 충족함) {
            picked.push_back(next);
            cnt += pick(n, picked, toPick-1)
            picked.pop_back();
        }
	}
}

요렇게 쓸 수 있다! 다음 코드의 이점은 다음과 같을 것이다.

글로벌 변수를 사용하지 않고, basecase 내 실행문이 짧아지므로 코드의 가독성이 높아진다.
코드의 논리 구조가 한 번 보이기만 하면 다음부터 빠르게 읽을 수 있다.

4 끝

종만: "한 번 푼 문제를 다시 본다고 해서 배우는 것이 있을까 생각할 수도 있지만, 오히려 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 더 많습니다."

Daniel Oh

안녕하세요. 오도열입니다.

이전 포스트

[알고리즘 문제 해결 전략] 06.3 문제: 소풍 (문제 ID: PICNIC)

다음 포스트

[알고리즘 문제 해결 전략] 06.5 문제: 게임판 덮기 (문제 ID: BOARDCOVER)