programmers 퍼즐 조각 채우기

programmers

level 3 퍼즐 조각 채우기

---

문제 설명

위의 이미지 클릭하면 해당 문제로 이동합니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void find(vector<vector<int>> &mat, vector<pair<int, int>> &block, int m, int n, int target){
    vector<int> x = {-1, 1, 0, 0}, y = {0, 0, 1, -1};
    target == 0 ? mat[m][n] = 1 : mat[m][n] = 0;
    block.push_back({m,n});

    for(int i = 0; i < 4; i++){
        int next_row = m+x[i], next_col = n+y[i];
        if(next_row < mat.size() && next_row >= 0 && next_col < mat.size() && next_col >= 0){
            if(mat[next_row][next_col] == target) find(mat, block, next_row, next_col, target);
        }
    }
}

void normalize(vector<pair<int, int>> &before){
    vector<pair<int, int>> result = before;
    before.clear();
    int min_x = 100, min_y = 100;

    for(pair<int, int> i : result){
        if(min_x > i.first) min_x = i.first;
        if(min_y > i.second) min_y = i.second;
    }

    for(pair<int, int> i: result) before.push_back({i.first-min_x, i.second-min_y});

    sort(before.begin(), before.end());
}

vector<pair<int,int>> rotate(vector<pair<int, int>> before){
    int max = 0;
    for(pair<int,int> i : before){
        if(i.first > max) max = i.first;
        if(i.second > max) max = i.second;
    }

    vector<pair<int, int>> after;

    for(pair<int, int> i : before) after.push_back({i.second, max-i.first});

    normalize(after);

    return after;
}

bool fit(vector<pair<int, int>> vac, vector<pair<int, int>> puz){
    vector<pair<int, int>> temp = puz;
    if(vac == temp) return true;

    for(int k = 0; k < 3; k++){
        temp = rotate(temp);
        if(vac == temp) return true;
    }

    return false;

}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0, size = game_board.size();
    vector<vector<pair<int, int>>> vacancy, puzzle;
    vector<vector<int>> test_game_board = game_board, test_table = table;

    for(int i = 0; i < size; i++){
        for(int j = 0; j < size; j++){
            if(test_game_board[i][j] == 0){
                vector<pair<int, int>> temp;
                find(test_game_board, temp, i, j, 0);
                normalize(temp);
                vacancy.push_back(temp);
            }
            if(test_table[i][j] == 1){
                vector<pair<int, int>> temp;
                find(test_table, temp, i, j, 1);
                normalize(temp);
                puzzle.push_back(temp);
            }
        }
    }

    vector<int> filled(vacancy.size(), 0);
    vector<int> used(puzzle.size(), 0);

    for(int i = 0; i < vacancy.size(); i++){
        for(int j = 0; j < puzzle.size(); j++){
            int v_size = vacancy[i].size(), p_size = puzzle[j].size();
            if(filled[i] != 1 && used[j] != 1 && v_size == p_size && fit(vacancy[i], puzzle[j])){
                filled[i] = 1;
                used[j] = 1;
                answer+=vacancy[i].size();
            }
        }
    }

    return answer;
}

---

해결 과정

어려운 알고리즘의 적용을 요구하는 게 아니고 구현이 어려운 문제였다. 문제의 요구사항을 하나씩 해결하면 풀 수 있다.

1. 도형을 돌리는 방법에 대해 생각해보았고 직접 그려가면서 간단한 연산식을 얻어서 적용하였다.

2. 주어진 행렬에서 도형을 찾는 방법으로 dfs이용해서 좌표값들을 pair로, 전체 도형을 vector로 저장해줬다.

3. 좌표값들을 0,0을 기준으로 당겨주었다.

4. 도형 회전시에 생기는 빈 공간을 없애는 방법을 적용했다.

5. 각각의 빈칸과 도형을 비교하고 정답을 반환했다.

아쉬운 점

도형과 빈칸을 추출하고 비교하는 과정에서 시간복잡도를 줄일 수 있을 것 같다.