[백준 c++] 14391 종이 조각

문제 설명

https://www.acmicpc.net/problem/14391
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.
종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력
첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)
둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력
영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

아이디어

비트마스킹을 이용한 풀이

2차원 배열을 2진수 비트로 표현

ex) n=2, m=3
000		000		000 	...
001		010		011
이런식으로 표현할 수 있음

dfs로 1이면 세로방향으로 탐색하고 0이면 가로 방향으로 탐색
각 숫자는 문자열로 이어붙이고 stoi(string)
123			 110
312		-> 	 110   -> (13)+(21)+3+2

전체 코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;
int n, m, y, x, bit, res, mx = -1, a[4][4], b[4][4], visited[4][4], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
string s;

void yd(int y, int x)
{
    s += to_string(a[y][x]);
    for (int i = 0; i < 4; i++)
    {
        int ny = dy[i] + y;
        if (ny < 0 || ny >= n || visited[ny][x] || !b[ny][x])
            continue;
        visited[ny][x] = 1;
        yd(ny, x);
    }
}

void xd(int y, int x)
{
    s += to_string(a[y][x]);
    for (int i = 0; i < 4; i++)
    {
        int nx = dx[i] + x;
        if (nx < 0 || nx >= m || visited[y][nx] || b[y][nx])
            continue;
        visited[y][nx] = 1;
        xd(y, nx);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%1d", &a[i][j]);
        }
    }

    for (int i = 0; i < (1 << n * m); i++)
    {
        fill(&visited[0][0], &visited[0][0] + 4 * 4, 0);
        fill(&b[0][0], &b[0][0] + 4 * 4, 0);
        x = 0, y = 0, s = "", res = 0;

        for (int j = 0; j < n * m; j++)
        {
            if ((i & (1 << j)))
                bit = 1;

            else
                bit = 0;

            if (x == m - 1)
            {
                b[y][x] = bit;
                x = 0, y++;
            }
            else
            {
                b[y][x] = bit;
                x++;
            }
        }

        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < m; k++)
            {
                if (!visited[j][k])
                {
                    s = "";
                    visited[j][k] = 1;
                    if (b[j][k])
                        yd(j, k);
                    else
                        xd(j, k);
                    res += stoi(s);
                }
            }
        }

        mx = max(mx, res);
    }
    cout << mx << "\n";
}