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

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

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

 

삼성 코딩테스트가 이번주 일요일로 코앞으로 다가왔기에 적어도 하루 2개씩은 풀어야한다..!

이 문제도 삼성다운 문제로 BFS + 구현문제이다. 이 문제는 오전문제인데 오후 1번 문제와 비슷한 결을 가지고 있다.

 

로직에 따른 모듈화를 잘해야한다. 무작정 코드를 짜면 안되고 함수들마다 책임과 일을 정확히 정하고 들어가야한다.

 

나의 경우는

 

- 맵 돌리기 함수

- 지금 현재 발굴 가능한 유적의 개수만 출력하는 함수

- 연쇄 발굴로 실제 유적 발굴

 

이렇게 나누었다. bfs도 발굴 가능한 유적의 개수만 출력하는 함수와 연쇄 발굴할 때 bfs가 약간의 차이가 있어 그냥 안에서 각자 구현하였다. 그리고 삼성은 이 문제처럼 행렬을 돌리는 것을 좋아하는데 숫자가 적으면 이 일일이 하드코딩할 수 있지만 너무 많으면 반복문을 통해 회전시키는 것이 좋다.

 

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

    int K, M;
    int dx[] = {1,-1,0,0};
    int dy[] = {0,0,1,-1};
    int letter_idx = 0;
    vector<vector<int>> historicsite(5, vector<int>(5));
    vector<int> letter;

    void print(vector<vector<int>> vec){
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                cout << vec[i][j] << ' ';
            }
            cout << endl;
        }
        cout << endl;
    }   
    
    vector<vector<int>> lotation_maps(int x, int y, int rad){ // 회전해서 리턴
        vector<vector<int>> result = historicsite;

        for(int i = 0; i < rad; i++){
            int tmp = result[x - 1][y - 1];
            result[x - 1][y - 1] = result[x + 1][y - 1];
            result[x + 1][y - 1] = result[x + 1][y + 1];
            result[x + 1][y + 1] = result[x - 1][y + 1];
            result[x - 1][y + 1] = tmp;

            tmp = result[x - 1][y];
            result[x - 1][y] = result[x][y - 1];
            result[x][y - 1] = result[x + 1][y];
            result[x + 1][y] = result[x][y + 1];
            result[x][y + 1] = tmp;
        }

        return result;
    }

    bool range(int x, int y) {
        return x < 5 && x > -1 && y < 5 && y > -1;
    }

    int Count_ruins(vector<vector<int>> maps){ // 유적의 개수를 새서 리턴
        bool check[5][5];
        int result = 0;
        memset(check, false, sizeof check);

        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                int value = maps[i][j];
                int cnt = 1;

                if(!check[i][j]){
                    queue<pair<int, int>> q;

                    q.push({i, j});
                    check[i][j] = true;

                    while(!q.empty()){
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();

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

                            if(range(nx, ny) && !check[nx][ny] && maps[nx][ny] == value){
                                check[nx][ny] = true;
                                cnt++;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
                if(cnt > 2) result += cnt;
            }
        }

        return result;
    }

    int recusion(vector<vector<int>> maps){
        bool check[5][5];
        int result = 0;

        memset(check, false, sizeof check);
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                if(!check[i][j]){
                    vector<pair<int, int>> points;

                    points.push_back({i, j});
                    int value = maps[i][j];

                    queue<pair<int, int>> q;

                    q.push({i, j});
                    check[i][j] = true;

                    while(!q.empty()){
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();

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

                            if(range(nx, ny) && !check[nx][ny] && maps[nx][ny] == value){
                                check[nx][ny] = true;
                                points.push_back({nx, ny});
                                q.push({nx, ny});
                            }
                        }
                    }
                
                    if(points.size() > 2){
                        for(pair<int, int> p : points){
                            maps[p.first][p.second] = -1;
                        }

                        result += points.size();
                    
                    }                 
                }
            }
        }

        // -1 인 부분 유적 채우기
        int pre = letter_idx;
        for(int j = 0; j < 5; j++){
            for(int i = 4; i > -1; i--){
                if(maps[i][j] == -1){
                    maps[i][j] = letter[letter_idx];
                    letter_idx++;
                }
            }
        }

        int after = letter_idx;

        if(pre == after) {
            historicsite = maps;
            return 0;
        }
        else return result + recusion(maps);
    }



    bool turn(){
        int row = 6, col = 6, rad = 4, maxCnt = 0;
        vector<vector<int>> next_map;

        for(int i = 1; i < 4; i++){
            for(int j = 1; j < 4; j++){
                for(int k = 1; k < 4; k++){
                    vector<vector<int>> tmp_maps = lotation_maps(i, j, k);
                    int cnt = Count_ruins(tmp_maps);

                    if(maxCnt < cnt){
                        row = i, col = j, rad = k, maxCnt = cnt, next_map = tmp_maps;
                    }else if(maxCnt == cnt){
                        if(rad > k){
                            row = i, col = j, rad = k, maxCnt = cnt, next_map = tmp_maps;
                        }else if(rad == k){
                            if(row > i){
                                row = i, col = j, rad = k, maxCnt = cnt, next_map = tmp_maps;
                            }else if(col > j){
                                row = i, col = j, rad = k, maxCnt = cnt, next_map = tmp_maps;
                            }
                        }
                    }
                    // if(i == 2 && j == 2){
                    //     cout << Count_ruins(tmp_maps) << endl;
                    // }
                }
            }
        }

        if(maxCnt > 2){
            cout << recusion(next_map) << ' ';

            return true;
        }

        return false;
    }

    int main(){
        cin >> K >> M;

        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                cin >> historicsite[i][j];
        for(int i = 0; i < M; i++){
            int tmp; cin >> tmp;
            letter.push_back(tmp);
        }

        for(int i = 0; i < K; i++){
            if(!turn()) break;
        }
    }