[코드트리] 예술성 (C++)

[문제]

https://www.codetree.ai/frequent-problems/artistry/description

코드트리

 

[풀이]

 

삼성전자 2022 상반기 오전 2번 문제.

N*N 격자에 대해 각 칸의 대한 색깔이 input으로 들어온다.

 

초기 예술 점수( 회전 안함) + 1회전 후 예술 점수 + 2회전 후 예술 점수 + 3회전 후 예술 점수를 출력해주면 된다.

 

1. 회전
2. 예술 점수 계산

각 step 별로 api를 구현하여 예술 점수를 계산하도록 했다.

 

초기에는 회전을 하지않고 예술 점수를 구하므로 calcScore api에서 예술 점수를 구하도록 했다.

 

calcScore에서는 BFS를 사용해 연속된 동일한 색깔끼리 그룹화를 하였다.

groupCnt를 통해 총 그룹의 개수를 저장

groupSize 배열에는 각 그룹에 대한 크기, groupIdx는 그룹에 해당하는 실제 색깔을 저장

또한 group 배열에는 grouping한 그룹의 index를 저장했다.

문제의 예시를 기준으로 보면 group 이차원 배열에는 다음과 같이 저장되어 있다.

1	2	2	3	3
2	2	2	3	3
2	2	4	3	4
2	2	4	4	4
2	2	4	4	4

그룹화를 마치면 calcTouch api에서 각 그룹별 맞닿는 변의 개수를 구하여 touch라는 이차원 배열에 저장해줬다.

각 칸 별로 아래 방향. 오른쪽 방향에 있는 칸을 확인하여 자신의 그룹과 다른 그룹이면 touch 배열의 [from][to]칸에 +1을 해주었다. 

각 칸 별로 아래, 오른쪽 방향에 대해서만  확인을 해주므로 두 개의 그룹이 맞닿는 변의 개수는 touch[from][to] + touch[to][from]이 된다.

 

이와 같이 맞닿는 변의 개수까지 구해주면 예술 점수를 구할 수 있다.

 

다음으로 rotate api를 통해 회전을 해주었다.

회전은 각 격자별 90도 시계 방향 회전이 있고 십자가 모양 부분을 90도 반시계 회전을 한다.

격자별 90도 시계 방향 회전을 인자가 다른 rotate api를 하나 더 선언하여 각 격자의 시작점을 인자 값으로 넘겨주었다.

 

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define MAX 30

using namespace std;

struct pos{
    int x,y;
};

int dx[4] ={ -1,0,1,0};
int dy[4] = {0,1,0,-1};

int N;
int map[MAX][MAX]={0,};
int group[MAX][MAX]={0,};
int touch[MAX*MAX][MAX*MAX]={0,};

void calcTouch()
{
    memset(touch, 0, sizeof(touch));

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int from = group[i][j];
            for(int k=1;k<=2;k++){
                int nx = i + dx[k];
                int ny = j + dy[k];
                
                if( nx <0 || ny <0 || nx >= N || ny >= N || group[nx][ny] == from)   continue;
                touch[from][group[nx][ny]]++;
            }
        }
    }
}

int calcScore()
{
    memset(group, 0, sizeof(group));

    int groupCnt=1;
    int groupSize[MAX*MAX]={0,};
    int groupIdx[MAX*MAX]={0,};
    queue<pos> q;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if( group[i][j] == 0){
                q.push({i,j});
                group[i][j]=groupCnt;
                groupIdx[groupCnt] = map[i][j];
                groupCnt+=1;
            }
            while(!q.empty()){
                int x= q.front().x;
                int y= q.front().y;
                q.pop();
                
                groupSize[group[x][y]]++;

                for(int k=0;k<4;k++){
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    
                    if( nx <0 || ny <0 || nx >= N || ny >= N || group[nx][ny] != 0)   continue;
                    if( map[nx][ny] != map[x][y])   continue;
                    
                    q.push({nx,ny});
                    group[nx][ny]=group[x][y];
                }
            }
        }
    }
    
    calcTouch(); // 맞닿는 변 개수 계산
    int score=0;
    for(int i=1;i<groupCnt;i++){
        for(int j=i+1;j<=groupCnt;j++){
            score += (groupSize[i]+groupSize[j]) * (touch[i][j]+touch[j][i]) * groupIdx[i] * groupIdx[j];
        }
    }
    return score;
}

void rotate(int x,int y)
{
    int len = (N-1)/2;
    
    int tmp[MAX][MAX]={0,};
    
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            tmp[j][len-1-i] = map[x+i][y+j];
        }
    }
    
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            map[x+i][y+j]=tmp[i][j];
        }
    }
    
}
void rotate()
{
    int len = (N-1)/2 + 1;
    
    rotate(0,0);
    rotate(0,len);
    rotate(len,0);
    rotate(len,len);

    int tmp[MAX]={0,};
    len-=1;
    
    for(int i=0;i<len;i++)  tmp[i] = map[i][len];
    for(int i=0;i<len;i++)  map[i][len] = map[len][N-1-i];
    for(int i=0;i<len;i++)  map[len][N-1-i]= map[N-1-i][len];
    for(int i=0;i<len;i++)  map[N-1-i][len]=map[len][i];
    for(int i=0;i<len;i++)  map[len][i]=tmp[i];

}

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    int score =0;
    
    score += calcScore();
    
    for(int i=0;i<3;i++){
        rotate();
        score += calcScore();
    }
    cout << score;
    return 0;
}