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

이 문제는 BFS, 시뮬레이션 문제이다.

 

이 문제에서 핵심은 부분 배열 회전, bfs 구현이다. 부분 배열 회전의 경우 이중 벡터와 함께 큐를 사용해서 구현했다. 좌표를 정확히 구현할 수도 있지만, 실제 코딩 테스트에서는 정확하고 빠르게 구현할 수 있는 직관적인게 좋다고 느꼈다. 보통 삼성 문제의 1번 문항은 구현력 위주고, 메모리나 성능에 대해서는 크게 걱정 안해도 되었기 때문에 이렇게 구현하는 게 나았다.

 

유물을 획득하는 것에 있어서는 bfs가 자신이 탐색한 위치들의 벡터를 리턴하도록 하여 구현했다. bfs 결과에 따라서 삭제할지 말지를 결정해야 하기 때문에 이를 리턴함으로써 사이즈가 3보다 작으면 삭제하지 않도록 했다.

 

침착하게 풀면 생각보다 쉽게 풀 수 있었다.

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

#define MAX 5

typedef vector<vector<int>> VVI;
typedef vector<int> VI;

VVI unit(MAX, VI(MAX, 0));
queue<int> restNumbers;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};
int K, M;

VVI pickSmall(int y, int x) {
    VVI result;

    for (int i = y - 1; i <= y + 1; i++) {
        VI temp;
        for (int j = x - 1; j <= x + 1; j++) {
            temp.push_back(unit[i][j]);
        }
        result.push_back(temp);
    }

    return result;
}

VVI rollSmall(VVI small, int counter) {
    VVI result = small;

    for (int i = 0; i < counter; i++) {
        VVI temp(3, VI(3, 0));
        
        temp[0][2] = result[0][0];
        temp[1][2] = result[0][1];
        temp[2][2] = result[0][2];
        temp[0][1] = result[1][0];
        temp[1][1] = result[1][1];
        temp[2][1] = result[1][2];
        temp[0][0] = result[2][0];
        temp[1][0] = result[2][1];
        temp[2][0] = result[2][2];

        result = temp;
    }

    return result;
}

VVI updateWhole(VVI& wholeUnit, VVI& rolled, int y, int x) {
    queue<int> q;
    
    for (VI& r : rolled) {
        for (int num : r) {
            q.push(num);
        }
    }

    for (int i = y - 1; i <= y + 1; i++) {
        for (int j = x - 1; j <= x + 1; j++) {
            wholeUnit[i][j] = q.front();
            q.pop();
        }
    }
    return wholeUnit;
}

bool inRange(int y, int x) {
    return (0 <= y && y < MAX && 0 <= x && x < MAX);
}

void print(VVI whole) {
    for (int y = 0; y < MAX; y++) {
        for (int x = 0; x < MAX; x++) {
            cout << whole[y][x] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}

vector<pair<int, int>> bfs(int startY, int startX, 
                            vector<vector<bool>>& visited, VVI& wholeUnit) {
    queue<pair<int, int>> q;
    vector<pair<int, int>> result;
    int number = wholeUnit[startY][startX];
    
    visited[startY][startX] = true;
    result.push_back({startY, startX});
    q.push({startY, startX});

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

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

            if (inRange(ny, nx) &&
                !visited[ny][nx] &&
                wholeUnit[ny][nx] == number) {
                
                result.push_back({ny, nx});
                q.push({ny, nx});
                visited[ny][nx] = true;
            }
        }
    }

    return result;
}

int calculateScore(VVI& wholeUnit) {
    vector<vector<bool>> visited(MAX, vector<bool>(MAX, false));
    int answer = 0;

    for (int y = 0; y < MAX; y++) {
        for (int x = 0; x < MAX; x++) {
            if (!visited[y][x]) {
                vector<pair<int, int>> result = bfs(y, x, visited, wholeUnit);

                if (result.size() >= 3) {
                    answer += result.size();
                }
            }
        }
    }

    return answer;
}

VVI traversal() {
    VVI result(MAX, VI(MAX, -1));
    int score = 0;

    for (int counter = 1; counter <= 3; counter++) {
        for (int x = 1; x <= 3; x++) {
            for (int y = 1; y <= 3; y++) {
                VVI small = pickSmall(y, x);
            
                VVI rolled = rollSmall(small, counter);
                
                VVI tempUnit = unit;
                
                VVI wholeUnit = updateWhole(tempUnit, rolled, y, x);
                int presentScore = calculateScore(wholeUnit);

                if (score < presentScore) {
                    result = wholeUnit;
                    score = presentScore;
                }
            }
        }
    }

    return result;
}

vector<pair<int, int>> findRemove() {
    vector<vector<bool>> visited(MAX, vector<bool>(MAX, false));
    vector<pair<int, int>> result;

    for (int y = 0; y < MAX; y++) {
        for (int x = 0; x < MAX; x++) {
            if (!visited[y][x]) {
                vector<pair<int, int>> temp = bfs(y, x, visited, unit);

                if (temp.size() >= 3) {
                    for (pair<int, int>& p: temp) {
                        result.push_back(p);
                    }
                }
            }
        }
    }

    return result;
}

int removeUnit() {
    vector<pair<int, int>> temp = findRemove();

    for (pair<int, int>& p : temp) {
        unit[p.first][p.second] = 0;
    }
    
    return temp.size();
}

void fillUnit() {
    for (int x = 0; x < MAX; x++) {
        for (int y = MAX - 1; y >= 0; y--) {
            if (unit[y][x] == 0) {
                unit[y][x] = restNumbers.front();
                restNumbers.pop();
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> K >> M;
    for (int y = 0; y < MAX; y++) {
        for (int x = 0; x < MAX; x++) {
            cin >> unit[y][x];
        }
    }
    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
        restNumbers.push(num);
    }

    for (int turn = 0; turn < K; turn++) {
        int answer = 0;
        VVI travUnit = traversal();

        //print(travUnit);

        if (travUnit[0][0] == -1) {
            break;
        }

        unit = travUnit;
        while (true) {
            int temp = removeUnit();
            if (temp == 0) {
                break;
            }
            answer += temp;
            
            fillUnit();
        }
        cout << answer << " ";
    }

    return 0;
}