백준 14391번 종이 조각[C++]

1. 문제 풀이

1-1. 문제 개요

 안녕하세요. 오늘 풀어볼 문제는 백준 14391번 종이 조각입니다. 문제의 유형은 비트마스킹을 활용한 브루트포스 알고리즘 응용문제였습니다. 브루트포스 알고리즘인 만큼 백트래킹을 사용하셔도 되고 여러 가지 구현을 사용하든 풀이가 가능합니다. 저는 비트마스킹이 익숙지 않기 때문에 공부해 볼 겸 비트마스킹을 사용해서 풀이했습니다.

 

1-2. 종이를 어떻게 자를지 선택하는 방법

 종이를 자르는 방법이 바로 이 문제의 핵심입니다. 종이를 자르는 방법은 가로와 세로 두 가지 경우밖에 없습니다. 종이의 크기는 N*M이고 각 칸을 가로로 자를지 세로로 자를지 결정하는 경우의 수는 2^(N*M)입니다.

 

 종이를 자르는 방법은 두 가지이므로 비트의 단위로 분석을 해보겠습니다. 임의의 칸을 가로로 자르기로 결정했다면 1, 세로로 자르기로 결정했다면 0이라고 해봅시다. 그렇다면 우리는 (N*M) 개의 비트로 모든 경우의 수를 따져볼 수 있습니다. 아래의 그림을 통해서 자세하게 알아봅시다.

 주어진 9개의 비트를 3 x 3 배열의 크기에 맞추어 그림과 같은 마스크라고 해봅시다. 위에서 가정한대로 1은 가로로 자를 칸이고 0은 세로로 자를 칸이 됩니다. 저 마스크에 맞춰서 종이를 자른다고 하면 아래와 같이 잘리게 됩니다.

 마스크를 사용하여 종이를 자르면 359 + 22 + 1 + 32 + 2 = 416임을 알 수 있습니다. 위와 같은 방법으로 어떤 칸을 어떻게 자를지 비트를 통해서 결정할 수 있고 모든 경우의 수를 따져본다면 000000000 ~ 111111111 까지 각 마스크를 사용해보면 됩니다.

 

1-3. 종이에서 자른 숫자를 구하는 방법

 종이를 어떻게 자를지 결정했다면 이제 마스크를 사용해서 각 잘린 종이의 숫자를 구할 수 있어야 합니다. 우리는 종이의 칸이 이미 잘린 부분인지 잘리지 않은 부분인지 구별할 수 없습니다. 이를 해결하기 위해 방문 배열을 선언해 이를 구분할 수 있게 합니다. 종이의 각 칸을 순회하면서 잘리지 않은 칸을 찾습니다. 찾았다면, 현재 칸의 비트마스크의 값을 찾아 그 값과 맞는 방향으로 이동하면서 숫자를 구해주시면 됩니다. 이동하면서 확인해야 할 조건들은 배열의 범위를 벗어나진 않는지, 비트 마스크의 값이 시작한 값의 비트마스크값과 같은지, 이미 방문한 칸인지 아닌지 확인하는 것이 필요합니다.

 

자세한 코드는 아래와 같습니다.

<  코드 >

int n, m;
int board[5][5];
bool vis[25];
bool is_row(int bit, int x, int y){ return (bit >> (x*m+y)) & 1; }
int get_num(int bit, int pos){
  int cx = pos / m;
  int cy = pos % m;
  int ret = board[cx][cy];
  bool flag = is_row(bit, cx, cy);
  vis[pos] = 1;
  flag ? ++cy : ++cx;
  while(cx < n && cy < m && !vis[cx*m + cy]){
    if(flag != is_row(bit, cx, cy)) break;
    vis[cx*m + cy] = 1;
    ret *= 10;
    ret += board[cx][cy];
    flag ? ++cy : ++cx;
  }
  return ret;
}

 

1-4. 시간복잡도 분석

 

비트 마스크의 모든 경우의 수 : 2^16 = 약 6만

종이를 잘라서 숫자를 구하는 경우의 수 : 16

 

시간복잡도 : O( 2^(N*M) )

 

시간제한이 2초이므로 무난하게 통과 가능

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define X first
#define Y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';
int n, m;
int board[5][5];
bool vis[25];
bool is_row(int bit, int x, int y){ return (bit >> (x*m+y)) & 1; }
int get_num(int bit, int pos){
  int cx = pos / m;
  int cy = pos % m;
  int ret = board[cx][cy];
  bool flag = is_row(bit, cx, cy);
  vis[pos] = 1;
  flag ? ++cy : ++cx;
  while(cx < n && cy < m && !vis[cx*m + cy]){
    if(flag != is_row(bit, cx, cy)) break;
    vis[cx*m + cy] = 1;
    ret *= 10;
    ret += board[cx][cy];
    flag ? ++cy : ++cx;
  }
  return ret;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    string line;
    cin >> line;
    for(int j = 0; j < m; j++){
      board[i][j] = line[j] - '0';
    }
  }
  // number of case : 경우의 수
  int ans{};
  int noc = 1 << (n * m);
  for(int bit = 0; bit < noc; bit++){
    int cur{};
    fill(vis, vis+n*m, 0);
    for(int i = 0; i < n * m; i++){
      if(!vis[i]) cur += get_num(bit, i);
    }
    ans = max(ans, cur);
  }
  cout << ans;
}

 

3. 제출 결과