[프로그래머스] 퍼즐 조각 채우기

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

프로그래머스

프로그래머스 - 퍼즐 조각 채우기

문제 유형 : bfs, 구현

문제 난이도 : Level 3

 

문제

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

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

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

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

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

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

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

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

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

 

풀이

 

조각이 빈 칸에 들어가기 위한 조건으로, 모양이 같아야 하지만, 더 우선으로, 크기가 같아야 합니다.
구멍의 크기가 더 작으면, 애초에 그 조각을 넣을 수 없을 것이고,
구멍의 크기가 더 크면, 조건 중에 있는 빈 공간이 있어서는 안 된다는 조건을 충족하지 못합니다.

따라서, 다음과 같이 풀 수 있습니다:

1. 각 2차원 배열(게임보드, 테이블)에서 빈 칸과 조각들을 찾아서 따로 저장해두기.
   • 여기서 저는 2차원 배열을 이용해서, 그 도형을 감싸는 최소 직사각형의 왼쪽 위의 좌표, 오른쪽 아래의 좌표, 크기를 저장했습니다.
   • 이는 bfs를 통해서 구할 수 있고, 이 정도는 쉬울 겁니다.
2. 이제 2차원 배열에 두 정보들이 있습니다.
   • 각 조각별로 각 빈칸 배열을 순회하며 비교하면서, 크기가 같으면, 두 직사각형의 값들을 체킹합니다.
   • 0도, 90도, 180도, 270도 회전도 시켜보면서 완전히 같은 도형인지 판단합니다. 이 중에서 한 번이라도 같은 도형임이 걸리면, 퍼즐을 넣을 수 있다는 뜻이지요. 이 구현은 아래 코드의 isMatch()를 참조하세요. 저는 각 좌표의 값의 비교를 xnor 연산으로 판별했습니다.
   • 넣고 나서는, 그 빈칸 정보는 2차원 배열에서 제거해야 합니다.
   • 조각과 빈 칸이 같음을 확인했다면, answer에 도형의 크기를 누적시키면 되겠습니다.
3. 이제 answer를 반환합니다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

bool isMatch(vector<int> &a, vector<int> &b, vector<vector<int>> &table, vector<vector<int>> &game_board) {
    int a_height = a[2] - a[0];
    int a_width = a[3] - a[1];
    int b_height = b[2] - b[0];
    int b_width = b[3] - b[1];

    if (a_height == b_height && a_width == b_width) {
        // 0, 180
        // 0
        bool flag = true;
        for (int i = 0; i <= a_height; i++) {
            for (int j = 0; j <= a_width; j++) {
                if (!(table[a[0] + i][a[1] + j] ^ game_board[b[0] + i][b[1] + j])) {
                    flag = false;
                }
            }
        }
        if (flag) return true;

        // 180
        flag = true;
        for (int i = 0; i <= a_height; i++) {
            for (int j = 0; j <= a_width; j++) {
                if (!(table[a[2] - i][a[3] - j] ^ game_board[b[0] + i][b[1] + j])) {
                    flag = false;
                }
            }
        }

        if(flag) return true;
    }
    if (a_height == b_width && a_width == b_height) {
        // 90, 270
        // 90
        bool flag = true;
        for (int i = 0; i <= a_width; i++) {
            for (int j = 0; j <= a_height; j++) {
                if (!(table[a[2] - j][a[1] + i] ^ game_board[b[0] + i][b[1] + j])) {
                    flag = false;
                }
            }
        }
        if (flag) return true;

        // 270
        for (int i = 0; i <= a_width; i++) {
            for (int j = 0; j <= a_height; j++) {
                if (!(table[a[0] + j][a[3] - i] ^ game_board[b[0] + i][b[1] + j])) {
                    return false;
                }
            }
        }
        return true;
    } else return false;
}

vector<int> bfs(int row, int col, int target, vector<vector<bool>> &visited, vector<vector<int>> &table) {
    vector<int> res = {n + 1, n + 1, -1, -1, 0};
    queue<pair<int, int>> q;
    q.push({row, col});
    visited[row][col] = true;

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        res[0] = min(res[0], curr.first);
        res[1] = min(res[1], curr.second);
        res[2] = max(res[2], curr.first);
        res[3] = max(res[3], curr.second);
        res[4]++;

        for (int i = 0; i < 4; i++) {
            int nr = curr.first + dr[i];
            int nc = curr.second + dc[i];

            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (!visited[nr][nc] && table[nr][nc] == target) {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }

    return res;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0;
    n = table.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    // [topleft_row, topleft_col, bottomright_row, bottomright_col, size]
    vector<vector<int>> fragments;
    // 빈 공간
    vector<vector<int>> board_empty;

    // 테이블 조각부터 찾자...
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && table[i][j] == 1) {
                fragments.push_back(bfs(i, j, 1, visited, table));
            }
        }
    }

    visited.assign(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && game_board[i][j] == 0)
                board_empty.push_back(bfs(i, j, 0, visited, game_board));
        }
    }

    for (auto fragment : fragments) {
        for (int i = 0; i < board_empty.size(); i++) {
            if (fragment[4] == board_empty[i][4]) {
                if (isMatch(fragment, board_empty[i], table, game_board)) {
                    board_empty.erase(board_empty.begin() + i);
                    answer += fragment[4];
                    break;
                }
            }
        }
    }

    return answer;
}