예술성

https://www.codetree.ai/training-field/frequent-problems/problems/artistry/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

재귀는 시간이 많이 걸린다.

풀다가 더러워진다면

다른 풀이가 있는지 생각해보자.

 

2개를 고른다고 아무 생각 없이 

브루트포스를 이용한 조합을 사용하면

시간 초과가 난다. (구현도 엄청 어렵다.)

 

1. ddang() 함수

map 전체를 돌면서

BFS를 한다.

groups 구조체 배열에 

{what_num, cnt}를 넣는다.

group_map에 group 번호를 넣는다.

 

2. Art_Score()

for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 0; k < 4; k++)

 

group_map의 값이 다르다면

(그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값

을 더해준다.

 

이렇게 하면 변 개수를 cnt 할 필요가 없다.

(그리고, 이러면 시간이 늘어나고 더 복잡해진다.)

 

중복 카운트를 했으므로

마지막에 나누기 2를 해주면 끝이다.

return art_score / 2;

 

 

<배열 돌리기>

 

이거 구현하면 된다.

2중 for문 변수 4개

 

<소스 코드>

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
 
using namespace std;
 
int n;
 
int map[33][33];
// 그룹 번호가 들어가는 맵
int group_map[33][33];
bool chk[33][33];
 
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0,0,-1, 1 };
 
struct g_info {
    int what_num;
    int cnt;
};
 
vector<g_info> groups;
int group_now = 0;
 
// 번호와 몇 개가 있는지를 구하는 bfs
void ddang(int r, int c)
{
    int num = map[r][c];
    int tmp_cnt = 1;
    int tmp[11] = { 0, };
 
    queue<pair<int, int>> q;
    q.push({ r,c });
    chk[r][c] = true;
    group_map[r][c] = group_now;
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
            {
                if (!chk[nx][ny] && (map[nx][ny] == num))
                {
                    chk[nx][ny] = true;
                    group_map[nx][ny] = group_now;
                    q.push({ nx, ny });
                    tmp_cnt++;
                }
            }
        }
    }
    groups.push_back({ num, tmp_cnt });
}
 
int ans = 0;
 
int ArtScore()
{
    int art_score = 0;
    bool visited[33][33] = { false, };
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
                {
                    if (group_map[i][j] != group_map[nx][ny])
                    {
                        int g1 = group_map[i][j];
                        int g2 = group_map[nx][ny];
 
                        art_score += (groups[g1].cnt + groups[g2].cnt) * groups[g1].what_num * groups[g2].what_num;
                    }
 
                }
            }
        }
    }
    return art_score / 2;
}
 
 
void kaisen()
{
    int mid = (n / 2) + 1;
 
    // 십자 모양 반시계 회전
    int down_arr[33];
    int left_arr[33];
    for (int i = 1; i <= n; i++)
        down_arr[i] = map[i][mid];
 
    for (int j = n; j >= 1; j--)
        left_arr[n - (j - 1)] = map[mid][j];
 
    for (int i = 1; i <= n; i++)
        map[i][mid] = left_arr[i];
 
    for (int j = 1; j <= n; j++)
        map[mid][j] = down_arr[j];
 
    // 사각형 시계 방향 회전
    // 여기에 회전 시킨거를 그냥 넣어버린다
    // 최고 크기가 14
    int tmp[33][33];
    memset(tmp, 0, sizeof(tmp));
 
    // 첫번째 사각형
    for (int i = 1; i <= (n / 2); i++)
    {
        for (int j = 1; j <= (n / 2); j++)
        {
            tmp[i][j] = map[i][j];
        }
    }
 
    for (int j = (n / 2), x = 1; j >= 1; j--, x++)
    {
        for (int i = 1, y = 1; i <= (n / 2); i++, y++)
        {
            map[i][j] = tmp[x][y];
        }
    }
 
    // 두번째 사각형
    for (int i = 1; i <= (n / 2); i++)
    {
        for (int j = mid + 1; j <= n; j++)
        {
            tmp[i][j] = map[i][j];
        }
    }
 
    for (int j = n, x = 1; j >= (mid + 1); j--, x++)
    {
        for (int i = 1, y = mid + 1; i <= (n / 2); i++, y++)
        {
            map[i][j] = tmp[x][y];
        }
    }
 
    // 세번째 사각형
    for (int i = mid + 1; i <= n; i++)
    {
        for (int j = 1; j <= (n / 2); j++)
        {
            tmp[i][j] = map[i][j];
        }
    }
 
    for (int j = (n / 2), x = mid + 1; j >= 1; j--, x++)
    {
        for (int i = mid + 1, y = 1; i <= n; i++, y++)
        {
            map[i][j] = tmp[x][y];
        }
    }
 
    // 네번째 사각형
    for (int i = mid + 1; i <= n; i++)
    {
        for (int j = mid + 1; j <= n; j++)
        {
            tmp[i][j] = map[i][j];
        }
    }
 
    for (int j = n, x = mid + 1; j >= (mid + 1); j--, x++)
    {
        for (int i = mid + 1, y = mid + 1; i <= n; i++, y++)
        {
            map[i][j] = tmp[x][y];
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];
    }
 
    for (int turn = 0; turn < 4; turn++)
    {
        memset(chk, false, sizeof(chk));
        groups.clear();
 
        group_now = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (!chk[i][j])
                {
                    ddang(i, j);
                    group_now++;
                }
            }
        }
 
        ans += ArtScore();
        kaisen();
    }
 
    cout << ans << '\n';
    return 0;
}