[코드트리] 고대 문명 유적 탐사 (c++) 구현

출처 : https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=2&pageSize=5

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

 

풀이 방법

구현 문제이기 때문에 구현해야 할 함수들만 잘 정리해서 구현해 주면 된다.

 

1. rotate_90(int y, int x, int cnt):

 

• 특정 좌표 (y, x)를 중심으로 시계 방향으로 cnt만큼 90도 회전시킨다.

• 회전할 3x3 영역의 좌표 값을 미리 rotate 배열에 저장하고, 해당 배열의 값을 시계 방향으로 회전하여 새로운 위치에 대입한다.

• cnt 만큼 회전한다 즉 cnt = 1, 2, 3 (90, 180, 270도 가능)

 

2. bfs(int y, int x):

 

• 특정 좌표에서 시작하여 BFS를 통해 같은 유물 번호를 가진 인접한 유물들을 찾는다.

• 인접한 유물이 3개 이상일 경우 이를 제거하고, 제거한 유물의 개수를 반환한다.

• 유물 번호가 같은 인접한 유물이 3개 이상이 아니면 제거하지 않는다.

 

3. find_remove():

 

• 5x5 격자 전체를 탐색하면서, 아직 방문하지 않은 유물이 있으면 BFS를 호출하여 해당 유물을 제거한다.

• 제거된 유물의 총 개수를 반환한다.

 

4. fill_artifacts(int idx):

 

• 제거된 유물로 인해 생긴 빈 공간에 새로운 유물 조각을 채워 넣는 함수이다. 조각은 아래쪽부터 채워지며, 조각 배열 piece의 인덱스 idx를 사용한다.

• 만약 유물 조각을 제일 많이 획득할 수 있는 경우로 선택된 경우 조각 배열의 인덱스인 piece를 업데이트해주고, 최대 획득 가능한 유물 조각을 찾는 경우라면 업데이트하지 않는 방법으로 백트레킹한다.

 

5. run(int y, int x, int turn, int fill_idx):

 

• 특정 좌표 (y, x)를 중심으로 turn번 회전한 후, 유물을 제거하고 점수를 계산한다.

• 유물을 제거한 후 새로운 유물 조각을 채워넣으며, 반복적으로 제거 및 채우기를 수행한다.

• 처음 제거된 유물의 개수와, 모든 제거 과정에서 얻은 총점수를 반환한다.

 

6. copy_ground_to_temp() 및 copy_temp_to_ground():

 

• ground 배열을 temp 배열로 복사하거나, 반대로 temp 배열을 ground 배열로 복사한다.

• 위 함수를 사용하여 백트레킹을 한다.

 

7. seek_turn():

 

• 격자에서 중심 좌표 (y, x)를 (1, 1)부터 (3, 3)까지 순회하면서 모든 가능한 회전 각도를 시도해 본 후, 점수가 가장 높아지는 회전 위치와 각도를 찾는다.

• 우선순위 큐를 사용해 회전 후 얻을 수 있는 최대 점수를 기준으로 가장 적합한 회전 위치와 각도를 결정한다.

 

#include <iostream>
#include <memory.h>
#include <queue>
using namespace std;

int K, M, ans = 0;
int ground[5][5];
int temp[5][5];
int piece[301], piece_idx = 0;
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};
// 유물 얻을 수 있는 최대 치를 선택하고
// 같다면 각도가 가장 작은것을 선택하고
// 열이 가장 작은 구간, 행이 가장 작은 구간을 선택해라


// 90도 유적을 돌리는 함수 구현

void rotate_90(int y, int x, int cnt) { //y, x를 중심으로 cnt 만큼 시계방향으로 회전

    for (int i = 0;i < cnt;i++) {
        // 회전할 좌표를 미리 저장
        int rotate[8] = {
            temp[y-1][x-1],  // 좌상단
            temp[y-1][x],    // 상단중앙
            temp[y-1][x+1],  // 우상단
            temp[y][x-1],    // 좌중앙
            temp[y][x+1],    // 우중앙
            temp[y+1][x-1],  // 좌하단
            temp[y+1][x],    // 하단중앙
            temp[y+1][x+1]   // 우하단
        };

        // 시계 방향으로 90도 회전
        temp[y-1][x-1] = rotate[5];  // 좌상단 <- 좌하단
        temp[y-1][x]   = rotate[3];  // 상단중앙 <- 좌중앙
        temp[y-1][x+1] = rotate[0];  // 우상단 <- 좌상단
        temp[y][x-1]   = rotate[6];  // 좌중앙 <- 하단중앙
        temp[y][x+1]   = rotate[1];  // 우중앙 <- 상단중앙
        temp[y+1][x-1] = rotate[7];  // 좌하단 <- 우하단
        temp[y+1][x]   = rotate[4];  // 하단중앙 <- 우중앙
        temp[y+1][x+1] = rotate[2];  // 우하단 <- 우상단
    } 
}
int visited[5][5];
int bfs(int y, int x) {    
    queue<pair<int, int> > q;
    vector<pair<int, int> > v;        
    int num = temp[y][x]; // 현재 유물 번호    
    if(num == 0) return 0;
    q.push(make_pair(y, x));
    visited[y][x] = 1;
    v.push_back(make_pair(y, x));
    while(!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if (ny < 0 || ny > 4 || nx < 0 || nx > 4) continue;
            if (visited[ny][nx] == 1) continue;
            if (num == temp[ny][nx]) { // 유물 번호가 같은 경우                                   
                q.push(make_pair(ny, nx));             
                visited[ny][nx] = 1;
                v.push_back(make_pair(ny, nx)); // 제거 해야할 땅 추가
            }
        }
    }
    if (v.size() >= 3) { // 3개 이상 뭉쳐 있을 때 제거
        for (int i = 0;i < v.size();i++) {            
            temp[v[i].first][v[i].second] = 0;            
        }        
        return v.size();
    }
    else return 0;
}

// 유적을 찾아 제거하고 점수를 반환하는 함수 구현
int find_remove() {
    int cnt = 0;    
    memset(visited, 0, sizeof(visited));
    for (int i = 0;i < 5;i++) {
        for (int j = 0;j < 5;j++) {
            if (visited[i][j] == 0) {                 
                cnt += bfs(i, j);
            }
        }
    }
    return cnt;
}


// 유적을 채워넣는 함수
void fill_artifacts(int idx) {
    for (int i = 0;i < 5;i++) { // x좌표를 더해가면서
        for (int j = 4;j >= 0;j--) { // y좌표를 빼가면서
            if (temp[j][i] == 0) {
                temp[j][i] = piece[idx];                
                idx++;                
            }
        }
    }    
}

// 어디를 돌릴지 판단하는 함수 구현 백트레킹으로 구현해야 한다. 
// 1. 완전 탐색으로 모든 곳을 돌려 본다.
// 2. 그 중 가장 점수를 많이 받을 수 있는 곳을 선택한다.
// 3. 위치와 방향을 모두 고려해야 한다.
// 1. 획득 가치가 최대인 경우
// 2. 회전 각도가 가장 작은 방법
// 3. 회전 중심 좌표의 열이 작고, 행이 작은 경우 x가 작고 y가 작은

struct Turn_locate {
    int y;
    int x;
    int value;
    int turn;
    Turn_locate(int y, int x, int value, int turn) : y(y), x(x), value(value), turn(turn){}

    bool operator < (const Turn_locate t) const {
        if (value < t.value) return true;
        else if (value == t.value) {
            if (turn > t.turn) return true;
            else if (turn == t.turn) {
                if (x > t.x) return true;
                else if (x == t.x) {
                    if (y > t.y) return true;
                    else return false;
                }
                else return false;
            }
            else return false;
        }
        else return false;
    }
};
pair<int, int> run(int y, int x, int turn, int fill_idx) { // 포인트 계산하는 함수
    rotate_90(y, x, turn); // turn 만큼 돌리고
    int ret = 0;
    int first_point = 0;
    while(true){ // 유물 제거
        int point = find_remove();               
        if (point == 0) break;
        if (first_point == 0) first_point = point;
        fill_artifacts(fill_idx); // 채워 넣기
        fill_idx += point;        
        ret += point;
    }     
    return make_pair(first_point, ret);
}

void copy_ground_to_temp() {
    for (int i = 0;i < 5;i++) {
        for (int j = 0;j < 5;j++) {
            temp[i][j] = ground[i][j];
        }
    }
}

void copy_temp_to_ground() {
    for (int i = 0;i < 5;i++) {
        for (int j = 0;j < 5;j++) {
            ground[i][j] = temp[i][j];
        }
    }
}
int seek_turn() {     
    priority_queue<Turn_locate> pq;
    for (int i =1;i < 4;i++) { // 어디를 회전할 지 판단하는 곳
        for (int j = 1;j < 4;j++) { // 중심 좌표는 1~4만 가능하다
            for (int k = 1;k < 4;k++) {                
                copy_ground_to_temp();
                pq.push(Turn_locate(i, j, run(i, j, k, piece_idx).first, k));                
            }
        }
    }
    Turn_locate tl = pq.top(); // 가장 많은 점수를 반환해 주는곳
    copy_ground_to_temp();
    int point = run(tl.y, tl.x, tl.turn, piece_idx).second; // 실제 반영하기 위한 run        
    piece_idx += point;      
    copy_temp_to_ground(); // 결정 되었으므로 temp를 ground에 반영하기       
    return point;
}

void input() {
    cin >> K >> M;
    for (int i = 0;i < 5;i++) {
        for (int j = 0;j < 5;j++) {
            cin >> ground[i][j]; 
        }
    }
    for (int i = 0;i < M;i++) { // 조각 입력 받기 
        cin >> piece[i];
    }
}

int main() {
    input();
    for (int i = 0;i < K;i++) {             
        int a = seek_turn();
        if (a == 0) break;
        cout << a << " ";
    }    
    return 0;
}