[코드트리] 예술성 with C++ (삼성기출)

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

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

 

언어: C++, 소요시간: 10ms

 

접근방법

그룹별 인접한 변의 개수를 찾기 위해 bfs(flood fill)을 2번 돌렸다.

첫 번째 bfs: 각 그룹의 시작 좌표(y, x), 그룹넘버를 groupMAP에 저장, 각 그룹별 칸의 개수 파악

두 번째 bfs: 각 그룹마다 인접한 그룹의 개수, 즉 변의 개수를 adjacentMAP에 저장

→ 그룹의 최대 가짓수는 29 x 29이므로, adjacentAMP은 여유롭게 900 x 900 2차원 배열로 만들었다.

여기엔 그룹마다 인접한 그룹의 변 수를 계산한다.

예를 들면 adjacentMAP[1][3] = 4라면, 그룹1과 그룹3이 이어진 변의 개수는 4라는 뜻이다.

 

구현시 고려사항

 

두 번째 bfs: 각 그룹마다 인접한 그룹 개수 구하기

첫 번째 bfs 돌릴때는 다들 쉽게 구현했을 것이다.

하지만 두 번째 bfs를 돌릴 때는 생각이 필요하다. ny nx를 돌릴때, 같은 그룹이라면 큐에 다시 넣어주고

다른 그룹이라면 adjacentMAP[현재그룹][새그룹] ++ 을 해준다.

// 인접한 변 개수 찾기용 bfs
void bfs_adjacent(int startY, int startX) {
    int curGroup = groupMAP[startY][startX];
    queue <Node> q;
    q.push({ startY, startX });
    visited[startY][startX] = 1;

    while (!q.empty()){
        Node now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = now.y + dy[i];
            int nx = now.x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N)    continue;
            if (visited[ny][nx] == 1)    continue;

            int adjacentGroup = groupMAP[ny][nx];
            if (adjacentGroup == curGroup) {        // 같은 그룹이면 계속 bfs 돌림
                q.push({ ny, nx });
                visited[ny][nx] = 1;
            }
            else {
                adjacentMAP[curGroup][adjacentGroup]++;
            }              
        }
    }
}

 

 

십자가 위치 → 반시계 회전

십자가 위치에 해당하는 위치를 벡터에 담고, 공식을 이용해 반시계 회전해줬다. 

// cross는 십자가 위치의 좌표 {y, x}들이 담겨있는 구조체 벡터
for (Node i : cross)
        tempMAP[N - 1 - i.x][i.y] = MAP[i.y][i.x];

 

 

 

4개 정사각형 → 시계 회전

각기 작은 배열을 시계회전한다고 생각하면 된다. 각 작은 배열의 좌상단 위치를 파악하고, 작은 배열의 변의 길이를 알면 공식과 점의 평행이동을 이용해 쉽게 구할 수 있다.

  // 4개 정사각형 회전
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++) {
            int squreY = i * (N / 2 + 1);     // 각 작은 배열의 시작 y좌표
            int squreX = j * (N / 2 + 1);     // 각 작은 배열의 시작 x좌표
            
            for (int k = 0; k < N/2; k++){
                for (int l = 0; l < N/2; l++){
                    tempMAP[l + squreY][N/2 - 1 - k + squreX] = MAP[k + squreY][l + squreX];
                }
            }
        }
    }

 

 

 

 

최종코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Node {
    int y;
    int x;
};

struct group {    // 그룹의 중심좌표, 숫자, 숫자 개수
    int y;
    int x;
    int num;
    int cnt;
};

int N, totalGroupNum, answer;
int MAP[30][30];                // 숫자들 저장 (주어지는 맵)
int groupMAP[30][30];           // 각 칸마다 그룹 숫자 저장
int adjacentMAP[900][900];      // 맞닿아있는 변의 수 내용 담음
int visited[30][30];            // 맞닿아있는 변의 수 저장할때 쓸 visited
group groupList[900];           // 각 그룹들 정보

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


void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }
}

// 그룹 나누기용 bfs
int bfs(int startY, int startX, int groupNum) {

    queue <Node> q;
    int curNum = MAP[startY][startX];
    int curCnt = 1;
    q.push({ startY, startX });
    groupMAP[startY][startX] = groupNum;

    while (!q.empty()) {

        Node now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = now.y + dy[i];
            int nx = now.x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                continue;
            if (groupMAP[ny][nx] > 0)
                continue;
            if (MAP[ny][nx] != curNum)
                continue;

            q.push({ ny, nx });
            groupMAP[ny][nx] = groupNum;
            curCnt++;
        }
    }

    return curCnt;
}

// 인접한 변 개수 찾기용 bfs
void bfs_adjacent(int startY, int startX) {
    int curGroup = groupMAP[startY][startX];
    queue <Node> q;
    q.push({ startY, startX });
    visited[startY][startX] = 1;

    while (!q.empty()){
        Node now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = now.y + dy[i];
            int nx = now.x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                continue;
            if (visited[ny][nx] == 1)
                continue;

            int adjacentGroup = groupMAP[ny][nx];
            if (adjacentGroup == curGroup) {        // 같은 그룹이면 계속 bfs 돌림
                q.push({ ny, nx });
                visited[ny][nx] = 1;
            }
            else {
                adjacentMAP[curGroup][adjacentGroup]++;
            }              
        }
    }
}

// 그룹 만들고 그룹마다 인접한 변의 수 찾는 함수
void makeGoup() {

    // 필요한것들 초기화
    memset(groupList, 0, sizeof(groupList));
    memset(visited, 0, sizeof(visited));
    memset(groupMAP, 0, sizeof(groupMAP));
    memset(adjacentMAP, 0, sizeof(adjacentMAP));
    int groupNum = 1;

    // 각 그룹마다 시작좌표, 숫자, 숫자 개수 저장
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (groupMAP[i][j] == 0) {
                int cnt = bfs(i, j, groupNum);
                groupList[groupNum] = { i, j, MAP[i][j], cnt };

                groupNum++;
            }
        }
    }
    totalGroupNum = groupNum - 1;

    // 그룹끼리 맞닿아 있는 변의 수 정의하기
    for (int i = 1; i <= totalGroupNum; i++){
        int groupY = groupList[i].y;
        int groupX = groupList[i].x;    
        bfs_adjacent(groupY, groupX);
    }
}

// 예술점수 찾고 answer에 더하는 함수
void findArtScore() {
    for (int groupA = 1; groupA <= totalGroupNum; groupA++){
        for (int groupB = groupA; groupB <= totalGroupNum; groupB++){
            if (adjacentMAP[groupA][groupB] > 0) {

                int groupAcnt = groupList[groupA].cnt;
                int groupBcnt = groupList[groupB].cnt;
                int groupAnum = groupList[groupA].num;
                int groupBnum = groupList[groupB].num;
                answer += ((groupAcnt + groupBcnt) * groupAnum * groupBnum * adjacentMAP[groupA][groupB]);           
            }
        }
    }
}

// 맵 회전하는 함수
void rotateMAP() {

    int tempMAP[30][30] = {0,};

    // 십자가 회전
    vector <Node> cross;
    Node middle = { N / 2, N / 2 };
    cross.push_back(middle);
    for (int i = 0; i < 4; i++){
        int offset = 1;
        while (1){
            int ny = middle.y + dy[i] * offset;
            int nx = middle.x + dx[i] * offset;

            if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                break;

            cross.push_back({ ny, nx });
            offset++;
        }
    }
    for (Node i : cross)
        tempMAP[N - 1 - i.x][i.y] = MAP[i.y][i.x];

    // 4개 정사각형 회전
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++) {
            int squreY = i * (N / 2 + 1);
            int squreX = j * (N / 2 + 1);

            for (int k = 0; k < N/2; k++){
                for (int l = 0; l < N/2; l++){
                    tempMAP[l + squreY][N/2 - 1 - k + squreX] = MAP[k + squreY][l + squreX];
                }
            }
        }
    }

    // 기존 맵에 업데이트
    memcpy(MAP, tempMAP, sizeof(MAP));
}

void solve() {
    for (int i = 0; i < 4; i++) {
        makeGoup();
        findArtScore();
        rotateMAP();
    }
    cout << answer;
}


int main() {
    //freopen("sample_input.txt", "r", stdin);
    input();
    solve();

    return 0;
}