[프로그래머스 위클리 챌린지 3주차] 퍼즐 조각 맞추기 (구현, BFS) [C++]

https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차

퍼즐 조각 채우기

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

빈칸에 도형을 채워서 최대로 몇 칸을 채울 수 있는지 구하는 문제이다.

단, 빈칸과 도형의 모양이 일치해야 하고 (빈칸이 있으면 안 된다), 도형은 회전이 가능하다.

 

내가 푼 방식은

1. BFS를 통해서 game_board에서 빈칸(x, y)을 저장, table을 돌면서 어떤 도형이 있는지 저장했다.
2. 빈칸의 모양과 도형의 모양을 찾았으면 이 도형이 빈칸에 일치하는지 확인해야 한다.
   • 그러나 위치가 다 달라서 하나하나 좌표를 비교하기는 매우 힘들다고 판단했다.
   • 따라서, 도형의 좌표를 모두 0,0 쪽으로 모아주었다.
   • 만약 1,0 2,0 3,0 인 크기 3인 기다란 도형이 있으면 변환을 통해서 0,0 1,0 2,0으로 옮겨주었다.
3. 이후, 도형은 회전이 가능하므로 도형을 회전 좌표변환을 통해서 90, 180, 270, 360 회전한 도형의 좌표를 저장해준다. 그리고, 빈칸과 마찬가지로 0,0 쪽으로 좌표를 모아주었다.
4. 마지막으로 좌표끼리 맞는지 비교를 해야 하는데, {0,0 1,0 2,0}이나 {2,0 0,0 1,0} 은 같은 도형이지만 비교할 때 불편하다.
   • 2중 for문으로 하나하나 맞았나 확인하고, 체크하고 하기엔 너무 힘들다고 판단했다.
5. 따라서 빈칸 좌표, 도형 좌표 모두 정렬해주었다.
6. 이후에 하나의 빈칸마다 모든 도형 * 각 도형의 회전 모양 4개를 비교해주었고, 만약 회전 도형 중 하나가 빈칸에 정확히 일치했을 경우 check배열을 통해서 그 도형을 다음 비교할 때 사용하지 않도록 해주었다.

---

코드 길이가 100줄이 넘어간다. 구현 문제라 어쩔 수 없는 것 같다.

 

1) BFS 함수

일반 BFS와 같다. 하지만 리턴 값을 도형 하나의 좌표 쌍 벡터를 리턴하도록 했다. 또한 target 파라미터를 만들었다.

입력값을 보면 game_board는 0을 찾아야 하고, table은 1을 찾아야 해서 함수를 재활용하기 위해 만들었다.

 

2) convert 함수

도형의 좌표 중에 최솟값을 찾아서 빼주었다.

0,2 0,3 1,3 2,3 2,4라는 도형이 있으면 x좌표의 최솟값과 y좌표의 최솟값을 구해서 빼주면 된다.

빈 공간을 변환하는 것과 도형을 변환하는 것에 차이점을 두었는데

빈 공간은 위의 방법대로 그냥 최솟값을 빼주었고, 도형은 회전을 하면 -값이 나오는 경우가 생긴다.

그래서 최솟값을 구하는 초기값 value에 차이를 주었다.

빈 공간은 50 x 50 이므로 넉넉히 100을 주었고 도형은 회전했을 경우 -가 나오면 0 이상으로 만들어야 했기에 최솟값의 초기값을 0으로 주었다.

 

3) rotation 함수

이건 나름 간단했다.

중, 고등학교 때 배웠던 회전 행렬을 통해 x' = -y, y' = x로 바꿔주었다.

90도 회전이므로 이걸 총 4번 진행했다. 

 

이후에 빈 공간의 좌표와 도형의 좌표를 비교하면서 모든 좌표가 일치하면 도형의 사이즈만큼 더해주었다.

크기가 일치해야 하므로 공간의 사이즈와 도형의 사이즈가 맞지 않으면 처음부터 비교하지 않았고

도형을 하나 사용하면 check를 통해서 다음에는 사용하지 않았다.

 

• + for(auto k : vector <vector <pii>> temp)에서 내부 좌표 배열을 정렬하려고 sort(k.begin(), k.end())를 했지만 정렬되지 않았다. 복사된 변수 k를 정렬했기 때문이다.
• + 도형 체크 배열을 처음엔 사이즈를 50으로 주었더니 일부 테스트 케이스를 통과하지 못했다. 아마도 테스트 케이스 중에 사이즈 1짜리 도형이 무수히 많은 케이스가 있나 보다. 그래서 50x50이므로 2500개로 늘려주었다.

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int xMove[4] = { 1, -1, 0, 0 }, yMove[4] = { 0, 0, 1, -1 }, check[51][51];

vector<pii> BFS(vector<vector<int>>& input, int x, int y, int target) {
    queue<pii> q;
    vector<pii> result;
    q.push({ x,y });
    result.push_back({ x,y });
    check[x][y] = true;

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

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

            if (nx >= 0 && nx < input.size() && ny >= 0 && ny < input.size()) {
                if (!check[nx][ny] && input[nx][ny] == target) {
                    check[nx][ny] = true;
                    q.push({ nx, ny });
                    result.push_back({ nx, ny });
                }
            }
        }
    }
    return result;
}

vector<vector<pii>> convert(vector<vector<pii>>& before, int value) {
    vector<vector<pii>> after;

    for (auto k : before) {
        int xMin = value, yMin = value;
        vector<pii> temp;
        for (auto i : k) {
            xMin = min(xMin, i.first);
            yMin = min(yMin, i.second);
        }
        for (auto i : k) {
            temp.push_back({ i.first - xMin, i.second - yMin });
        }
        after.push_back(temp);
    }
    return after;
}

vector<pii> rotation(vector<pii> input) { // x,y -> -y,x
    vector<pii> result;
    for (auto i : input) {
        int afterX = -i.second;
        int afterY = i.first;
        result.push_back({ afterX, afterY });
    } // 하나 도형 90도 회전 완료
    return result;
}

bool compare(pii a, pii b) {
    if (a.first == b.first)
        return a.second < b.second;
    else
        return a.first < b.first;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0;
    int inputSize = game_board.size();

    vector<vector<pii>> blanks;
    for (int i = 0; i < inputSize; i++) {
        for (int j = 0; j < inputSize; j++) {
            if (game_board[i][j] == 0 && !check[i][j])
                blanks.push_back(BFS(game_board, i, j, 0));
        }
    }
    // 값이 0이면 BFS 돌면서 빈 공간 저장해주기

    for (int i = 0; i < inputSize; i++) {
        for (int j = 0; j < inputSize; j++) {
            check[i][j] = false;
        }
    }
    // bfs 방문 체크 초기화

    vector<vector<pii>> shapes;
    for (int i = 0; i < inputSize; i++) {
        for (int j = 0; j < inputSize; j++) {
            if (table[i][j] == 1 && !check[i][j])
                shapes.push_back(BFS(table, i, j, 1));
        }
    }
    // 값이 1이면 BFS를 돌면서 도형의 좌표 저장해주기
    
    vector<vector<pii>> afterBlanks = convert(blanks, 100);
    for (int i = 0; i < afterBlanks.size(); i++) {
        sort(afterBlanks[i].begin(), afterBlanks[i].end(), compare);
    }
    // 빈 칸을 convert해주고 정렬해준다.
    
    vector<vector<pii>> afterShapes = convert(shapes, 100);
    // 도형도 convert한 상태에서 회전을 진행한다.

    vector<vector<vector<pii>>> finalShapes;
    for (auto k : afterShapes) { // k는 도형 덩어리 벡터 하나 vector<pii> k;
        vector<vector<pii>> afterTemp;
        for (int i = 0; i < 4; i++) {
            vector<pii> temp = rotation(k); // 도형 덩어리 자체를 90' 돌린다
            afterTemp.push_back(temp);
            k = temp;
        } // afterRotation에는 도형 덩어리 4방향 저장
        vector<vector<pii>> afterRotation = convert(afterTemp, 0);
        for (int i = 0; i < afterRotation.size(); i++) {
            sort(afterRotation[i].begin(), afterRotation[i].end(), compare);
        } // 도형 회전과 동시에 정렬해준다.
        finalShapes.push_back(afterRotation); // 모든 도형 저장
    }

    int tableCheck[2501] = { false, };

    for (int i = 0; i < afterBlanks.size(); i++) {
        vector<pii> blank = afterBlanks[i];
        bool shapeFlag = false;
        for (int j = 0; j < finalShapes.size(); j++) {// vector<vector<pii>> - 4방향
            if (tableCheck[j]) // 사용한 도형이면 pass
                continue;
            vector<vector<pii>> fourShapes = finalShapes[j];
            if (blank.size() != fourShapes[0].size())
                continue; // 도형 사이즈 자체 X
            for (auto shapes : fourShapes) { //  vector<pii> // 덩어리 하나
                int oneFlag = true; // 모든 좌표가 맞는지 확인하는 용도
                for (int k = 0; k < blank.size(); k++) {
                    pii bl = blank[k];
                    pii sh = shapes[k];
                    if (bl.first == sh.first && bl.second == sh.second)
                        continue;
                    else {
                        oneFlag = false;
                        break;
                    }
                }
                if (oneFlag) { // 4방향 중 하나가 맞았다.
                    shapeFlag = true;
                    answer += blank.size();
                    break;
                }
            }
            if (shapeFlag) {
                tableCheck[j] = true; // 그 도형 사용 X
                break;
            }
        }
    }
    return answer;
}