2234번 성곽

https://www.acmicpc.net/problem/2234

어려운 문제는 아니나, 자잘한 기능들을 구현하는데 귀찮은 문제이다.

내 생각엔 이 문제의 핵심은 그루핑(grouping, 그룹화, 그룹 저장 등)이다.

또한, 

오른쪽이나 왼쪽으로 갈 경우 4, 1에 대한 검사와

위아래로 갈 경우 2와 8에 대한 검사만 잘 해주면 된다.

각 숫자에 대한 bit가 어떤 숫자들로 구성되어있는지는 [행][열]에 대한 vector로 저장했다.

코드가 좀 긴 것 같고, 배열의 이름이 헷갈릴 수도 있겠다.

더 간결하고, 빠른 코드가 있을 것이다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> bit = { 1, 2, 4, 8 };
 
vector<int> Map[51][51];
 
int m, n; // m : 열, n : 행
 
int g[51 * 51], group_map[51][51];
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
bool visit[51][51];
 
void bit_search(vector<int> vc, int idx, int r, int c, int goal)
{
    if (accumulate(vc.begin(), vc.end(), 0) == goal)
    {
        Map[r][c] = vc;
        return;
    }
 
    for (int i = idx; i < bit.size(); i++)
    {
        vc.push_back(bit.at(i));
        bit_search(vc, i + 1, r, c, goal);
        vc.pop_back();
    }
}
 
bool chk(int y, int x, int s)
{
    for (auto i : Map[y][x])
        if (i == s)
            return true;
    return false;
}
 
int dfs(int r, int c, int group_number)
{
    int ret = 1;
 
    group_map[r][c] = group_number;
 
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= n || x < 0 || x >= m || visit[y][x]) continue;
 
        if (i == 0) // 오른쪽으로
        {
            if (chk(r, c, 4) || chk(y, x, 1)) continue;
        }
        else if (i == 1) // 아래로
        {
            if (chk(r, c, 8) || chk(y, x, 2)) continue;
        }
        else if (i == 2) // 왼쪽으로
        {
            if (chk(r, c, 1) || chk(y, x, 4)) continue;
        }
        else if (i == 3) // 위로
        {
            if (chk(r, c, 2) || chk(y, x, 8)) continue;
        }
 
        ret += dfs(y, x, group_number); // dfs(y, x, group_number) + 1 아님. ret의 초깃값이 1 이다.
    }
 
    return ret;
}
 
int main(void)
{
    int input, grouping = 1, Max = 0, Max_sum = 0;
 
    scanf("%d %d", &m, &n);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            vector<int> vc;
            scanf("%d", &input);
            bit_search(vc, 0, i, j, input);
        }
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)        
            if (!visit[i][j])
            {
                g[grouping] = dfs(i, j, grouping);
                Max = max(Max, g[grouping]);
                ++grouping;
            }
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)    
            for (int k = 0; k < 4; k++)
            {
                int y = i + dy[k];
                int x = j + dx[k];
 
                if (y < 0 || y >= n || x < 0 || x >= m || group_map[i][j] == group_map[y][x]) continue;
 
                Max_sum = max(Max_sum, g[group_map[i][j]] + g[group_map[y][x]]);
            }
    
    printf("%d\n%d\n%d\n", grouping - 1, Max, Max_sum);
 
    return 0;
}