[코드트리] 예술성 - 시뮬레이션, BFS/DFS (기출문제)

삼성 SW 역량테스트 2022 상반기 기출 

예술성

예술가 Sam은 그림에 대한 예술성을 평가하는 알고리즘을 만들어냈습니다. 그림을 편의상 n * n 크기의 격자로 생각하고, 각 칸의 색깔을 1이상 10이하의 숫자로 표현하여 이 알고리즘을 적용해보려 합니다.

다음은 5 * 5 크기의 그림의 예시입니다.

먼저 이 그림에서 동일한 숫자가 상하좌우로 인접해있는 경우 동일한 그룹이라 본다면, 총 4개의 그룹이 만들어지게 됩니다.

예술 점수는 모든 그룹 쌍의 조화로움의 합으로 정의됩니다. 그룹 a와 그룹 b의 조화로움은 (그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값 x 그룹 a와 그룹 b가 서로 맞닿아 있는 변의 수로 정의됩니다.

예로 <Figure 2> 에서 두 그룹 G2, G4의 조화로움은 (11 + 8) x 2 x 1 x 4 = 152가 됩니다.

그룹 쌍 간의 조화로움 값이 0보다 큰 조합인 (G1, G2), (G2, G3), (G2, G4), (G3, G4) 의 조화로움 값을 전부 더하면 48 + 192 + 152 + 156 = 548이 됩니다. 이를 초기 예술 점수라 부르겠습니다.

초기 예술 점수를 구한 뒤에는 그림에 대한 회전을 진행합니다.

회전은 정중을 기준으로 두 선을 그어 만들어지는 십자 모양과 그 외 부분으로 나뉘어 진행됩니다.

• 십자 모양의 경우 통째로 반시계 방향으로 90' 회전합니다.

• 십자 모양을 제외한 4개의 정사각형은 각각 개별적으로 시계 방향으로 90'씩 회전이 진행됩니다.

두 부분에 대한 회전이 동시에 진행되므로 회전 이후 <Figure 4>는 다음 모습이 됩니다.

이제 <Figure 7>의 예술 점수 역시 마찬가지 방법으로 구하면 442점이 됩니다. 이는 1회전 이후 예술 점수가 됩니다.

n * n 크기의 그림 정보가 주어졌을 때, 초기 예술 점수, 1회전 이후 예술 점수, 2회전 이후 예술 점수, 그리고 3회전 이후 예술 점수의 합을 구하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 n이 주어집니다. n은 반드시 홀수입니다.
이후 n개의 줄에 걸쳐 각 행에 칠해져 있는 색깔에 대한 정보인 숫자들이 공백을 사이에 두고 주어집니다.

• 3 ≤ n ≤ 29
• 1 ≤ 주어지는 숫자 ≤ 10

출력 형식

첫 번째 줄에 초기 예술 점수, 1회전 이후 예술 점수, 2회전 이후 예술 점수, 그리고 3회전 이후 예술 점수를 모두 합한 값을 출력합니다.

---

 

해설 참고하면서 풀었는데도

하나하나 이해하면서 다 따져가면서 푸느라 문제 읽는것부터 풀이 성공까지 총 3시간이 걸린 문제....

 

안녕하세요 도서관 지박령입니다

요즘 학교도서관이 밤 12시까지 운영하는데

오늘도 12시까지 공부하다가 옴 🤓

 

문제가 길고 요구사항이 많은 시뮬레이션 문제가 요즘 코테 트렌드라고 하네요,,,

많이 풀면서 익혀야 실력이 늘 것 같습니다!

 

예술성 문제는 삼성 기출 빡구현이고

dfs/bfs 응용력과 약간의 공간지각능력(?)이 필요한 듯 합니다

 

처음에 입력받고 나서 그룹번호에 따른 맵을 만들고, 어떤 그룹에 몇 개의 수가 있는지 모두 저장해놔야 합니다.

합계를 구하는 과정에서는 탐색 말고 이중반복문으로 구현해야 빼먹지 않고 합계를 구해낼 수 있습니다

그리고 중복되는 부분이 생기므로 2로 나눠줘야 함

 

마지막에 답이 계속 틀려서 헤멨는데, rotate할때마다 전역변수 visited 초기화를 안시켜줘서 틀린거였음!!

그래서 결국 그거까지 발견해서 고치고 성공했네요ㅠ

문제 풀때 과정마다 Map을 출력해서 보는게 큰 도움이 됩니다!

 

 

 

나의 풀이

#include <iostream>
#include <queue>
using namespace std;

int n;
int map[30][30];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int visited[30][30];
queue<pair<int,int>> q;
int groupMap[30][30]; // 그룹번호 맵
int groupNumCnt[900]; // 인덱스=그룹번호, 내용=갯수
int Sum = 0;
int rMap[30][30];

void findGroup(int x, int y, int groupNum){
    int tmp = map[x][y];
    int cnt=1;
    q.push({x,y});
    groupMap[x][y] = groupNum;
    visited[x][y] = 1;
    while(!q.empty()){
        pair<int,int> a = q.front();
        q.pop();
        for(int i=0;i<4;++i){
            int nx = a.first + dx[i];
            int ny = a.second + dy[i];
            if(nx<1 || ny<1 || nx>n || ny>n) continue; // 범위 체크
            if(visited[nx][ny] == 1) continue;
            if(map[nx][ny] == tmp){
                q.push({nx,ny});
                groupMap[nx][ny] = groupNum;
                visited[nx][ny] = 1;
                cnt++;
            }
        }
    }
    groupNumCnt[groupNum] = cnt;
}

void SumCount(){ // 이거 탐색으로 하면 체크 못하는 값이 생겨서 그냥 반복문으로 하기!!
    int nearSum = 0;
    for (int x = 1; x <= n; x++){
        for(int y = 1; y <= n; y++){
            for(int i=0;i<4;++i){ // 양옆, 아래 이동
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx<1 || ny<1 || nx>n || ny>n) continue; // 범위 체크
                if (map[x][y] != map[nx][ny]){ // 인접한 값이 다른 경우에
                    int num1 = map[x][y];
                    int num2 = map[nx][ny];
                    int cnt1 = groupNumCnt[groupMap[x][y]];
                    int cnt2 = groupNumCnt[groupMap[nx][ny]];
                    nearSum += (cnt1 + cnt2) * num1 * num2;
                }
            }
        }
    }
    // cout << nearSum / 2;
    Sum += (nearSum / 2);
}

void makeGroup(){
    int group_cnt = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n;++j){
            if(visited[i][j]==0){
                group_cnt++;
                findGroup(i, j, group_cnt);
            }
        }
    }
}

void rotateMini(int sx, int sy, int size){
    for (int i = sx; i < sx + size; ++i){
        for (int j = sy; j < sy + size; ++j){
            // 시작좌표를 0,0로 바꾸고 계산한뒤 다시 복구시켜서 저장
            int nx = i - sx;
            int ny = j - sy;
            int rx = ny;
            int ry = size - nx - 1;
            rMap[rx + sx][ry+sy] = map[i][j];
            // cout << i << " " << j << " - " << rx + sx << " " << ry+sy << "\n";
        }
    }
}

void rotateMap(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) { // 얘가문젠데
            // 세로줄은 (i, j) -> (j, i)
            if(j == (n+1) / 2)
                rMap[j][i] = map[i][j];
            // 가로줄은 (i, j) -> (n-j+1, i)?
            else if(i == (n+1) / 2)
                rMap[n - j + 1][i] = map[i][j];
        }
    }
    int mini = (n-1) / 2;
    rotateMini(1, 1, mini); // 시작좌표x,y, 사이즈
    rotateMini(1, mini+2, mini);
    rotateMini(mini+2, 1, mini);
    rotateMini(mini+2, mini+2, mini);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) {
            map[i][j] = rMap[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) {
            visited[i][j] = 0;
        }
    }
}

int main() {
    cin >> n;

    for(int i=1; i<=n; ++i){
        for(int j=1;j<=n;++j) cin >> map[i][j];
    }
    for (int i = 0; i < 4; ++i){
        makeGroup();
        SumCount();
        if(i<3) rotateMap();
    }
    cout << Sum;
    return 0;
}

 

코테 기출문제 처음 봤을때는 내가 풀 수 있는 수준이 아닌 것 같아서 겁만 잔뜩 먹었는데,

그래도 너무 막힐때는 풀이 참고해가며 매일매일 풀어보니까 자신감이 좀 붙는 것 같습니다

열심히 해야겠습니다~~