[프로그래머스 위클리 챌린지 3주차] 퍼즐 조각 채우기

문제

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

코딩테스트 연습 - 3주차

 

풀이

1. 우선 해야 하는 걸 간단하게 정리하자면 아래와 같습니다.

 

• 1. 게임 보드의 서로 인접한 빈 공간 좌표 집합들을 구합니다.
• 2. 테이블 위의 퍼즐 조각들 좌표 집합들을 구합니다.
• 3. (2)의 퍼즐 조각들을 회전시켜가며 (1)의 빈 조각 집합에 일치하는지 확인하면 됩니다. (한 퍼즐을 놓을 때, 보드의 남는 부분이 없어야 하기에 빈 공간의 크기와 퍼즐 조각들의 크기는 같아야 합니다.) 

 

2. (1), (2) 모두 bfs로 원하는 좌표 집합들을 구할 수 있지만 모양을 비교할 때 필요한 건 보드, 테이블 위에서 좌표들이 아니기에 구한 좌표들을 따로 처리하여 모양을 표현할 수 있게 바꿔줘야 합니다. 이는 아래와 같이 해결할 수 있습니다.

 

• 구한 좌표들을 모양으로 바로 표현할 수 없는 이유는 어디에서 얼마나 떨어졌는지가 각각이 다르기 때문입니다.
• 따라서 구한 좌표들의 x좌표, y좌표 값의 최소 값(offsetX, offsetY)을 찾은 뒤, 구한 좌표들에 대해 offset만큼 빼주면 원점으로부터 떨어진 위치를 표현하도록 고정할 수 있고, 비교가 가능해집니다.   

3. 퍼즐을 회전하는 부분은 각각의 좌표들을 시계 방향으로 45' 회전하듯이 (x, y) -> (y, -x)로 옮겨준 뒤, 앞서 offset처리를 한 것처럼 옮겨준 좌표에서의 offset만큼 빼서 회전할 수 있습니다. 

코드

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int dir[4][2] ={{-1,0},{1,0},{0,-1},{0,1}};
vector<vector<pii>> b, t;
int board[51][51], table[51][51], n;
bool vis[51][51], usedPuzzle[2501];

vector<pii> bfs (int x, int y, bool isTable){
    int offsetX = x, offsetY = y;
    vector<pii> ret;
    queue<pii> q;
    q.push({x, y});
    ret.push_back({x, y});
    vis[x][y] = 1;
    while(!q.empty()){
        auto [cx, cy] = q.front(); q.pop();
        for (int i = 0 ; i < 4; i++){
            int nx = cx + dir[i][0];
            int ny = cy + dir[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny]) continue;
            if (isTable && table[nx][ny] || !isTable && !board[nx][ny]){
                offsetX = min(offsetX, nx), offsetY = min(offsetY, ny);
                q.push({nx, ny});
                ret.push_back({nx, ny});
                vis[nx][ny] = 1;
            }
        }
    }
    for (auto &[x, y] : ret) x -= offsetX, y -= offsetY;
    return ret;
};

void rotate(vector<pii> &d){
    int offsetX = 123, offsetY = 123;
    for (auto &[x, y] : d){
        swap(x, y); y *= -1;
        offsetX = min(offsetX, x);
        offsetY = min(offsetY, y);
    }
    for (auto &[x, y] : ret) x -= offsetX, y -= offsetY;
}

// i번째 보드의 빈 공간 집합과 j번째 테이블의 퍼즐 집합을 매치할 수 있는가?
bool canMatch(int i, int j) {
    if (b[i].size() != t[j].size()) return 0;
    int emptyCount = b[i].size();
    vector<pii> targetPuzzleSet = t[j];
    for (int rep = 0; rep < 4; rep++){
        rotate(targetPuzzleSet);
        int matchCount = 0;
        for (auto [x1, y1] : b[i])
            for (auto [x2, y2] : targetPuzzleSet){
                if (x1 == x2 && y1 == y2){
                    matchCount++;
                    break;
                }
            }
        if (matchCount == emptyCount) return 1;
    }
    return 0;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> Table) {
    int answer = 0;
    n = Table.size();
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) board[i][j] = game_board[i][j];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) table[i][j] = Table[i][j];

    // (1) 게임 보드의 서로 인접한 빈 공간 좌표 집합들을 구함
    for (int i = 0 ; i < n; i++)
        for (int j = 0 ; j < n; j++)
            if (!vis[i][j] && !board[i][j])
                b.push_back(bfs(i, j, 0));

    memset(vis, 0, sizeof(vis));

    // (2) 테이블 위의 퍼즐 조각들 좌표 집합들을 구함
    for (int i = 0 ; i < n; i++)
        for (int j = 0 ; j < n; j++)
            if (!vis[i][j] && table[i][j])
                t.push_back(bfs(i, j, 1));

    for (int i = 0 ; i < b.size(); i++){
        for (int j = 0; j < t.size(); j++){
            if (usedPuzzle[j]) continue; // 사용한 퍼즐이면 무시
            if (canMatch(i, j)){ // 매칭이 된다면
                usedPuzzle[j] = 1;
                answer += t[j].size();
                break;
            }
        }
    }
    return answer;
}