퍼즐 조각 채우기 [Lv. 3] (C++)

프로그래머스

퍼즐과 퍼즐을 채워 넣을 게임보드를 입력 받습니다.

퍼즐을 보드에 최대한 채워넣을 수 있는 칸의 수를 구하여 출력하면 됩니다.

 

풀이 방법

문제는 크게 3개 단계로 구분됩니다.

1. 이차원 배열에서 각각의 퍼즐과 퍼즐을 채워넣을 공간 추출

2. 퍼즐과 공간 매칭

3. 퍼즐 90도 회전

 

1번의 경우 bfs로 퍼즐 보드를 탐색하여 추출할 수 있겠습니다.

visited.resize(table.size(), vector<bool>(table[0].size(), false));
for (int i = 0; i < table.size(); i++){
    for (int j = 0; j < table[i].size(); j++){
        if (!visited[i][j] && table[i][j] == 1)
            puzzles.push_back(bfs(table, i, j, 1));
    }
}

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

bfs로 퍼즐과 공간을 찾고 vector에 넣어줍니다.

 

bool check(vector<vector<int>>& table, int y, int x, int n)
{
    return y >= 0 && y < table.size() && x >= 0 && x < table[0].size() && table[y][x] == n; 
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<pair<int, int>> bfs(vector<vector<int>>& table, int y, int x, int n)
{
    vector<pair<int, int>> ret;
    queue<pair<int, int>> q;
    q.push({y, x});
    visited[y][x] = true;
        
    int minY = y, minX = x;
    
    while (!q.empty())
    {
        auto [cy, cx] = q.front(); q.pop();
        ret.push_back({cy, cx});
        
        for (int i = 0; i < 4; i++)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (check(table, ny, nx, n) && !visited[ny][nx])
            {
                q.push({ny, nx});
                visited[ny][nx] = true;

                minY = min(minY, ny);
                minX = min(minX, nx);
            }
        }
    }
    
    
    for (pair<int, int>& p : ret)
    {
        p.first -= minY;
        p.second -= minX;
    }
    return ret;
}

최소 Y, X 위치를 찾고 모든 값에 빼주어 0,0 부터 시작하게끔 하여 비교하기 쉽게 합니다.

 

추출이 끝나면 퍼즐과 공간을 비교합니다.

vector<bool> used(puzzles.size(), false);

int answer = 0;
for (auto& empty : empties){
    for (int i = 0; i < puzzles.size(); i++)
    {
        if (!used[i] && match(puzzles[i], empty))
        {
            used[i] = true;
            answer += puzzles[i].size();
            break;
        }
    }
}

퍼즐과 공간을 하나하나 match함수로 비교합니다.

이미 사용한 퍼즐이라면 건너뜁니다.

 

bool match(vector<pair<int, int>>& puzzle, vector<pair<int, int>>& empty)
{
    if (puzzle.size() != empty.size())
        return false;

    for (int r = 0; r < 4; r++)
    {
        int cnt = 0;
        for (pair<int, int>& e : empty)
        {
            for(pair<int, int>& p : puzzle)
            {
                if (p == e){
                    cnt++;
                    break;                
                }
            }
        }
        
        if (cnt == puzzle.size())
            return true;

        rot(puzzle);
    }
    
    return false;
}

퍼즐과 공간이 매칭이 된다면 true를 반환 매칭이 되지 않으면 rot 함수를 이용해 회전시킵니다.

 

void rot(vector<pair<int, int>>& v)
{
    int maxY = 0, minY = 100000, minX = 100000;
    for (auto& p : v)
        
    for (auto& p : v)
    {
        int temp = p.first;
        p.first = maxY - p.second;
        p.second = temp;
        
        minY = min(minY, p.first);
        minX = min(minX, p.second);
    }
    
    
    for (pair<int, int>& p : v)
    {
        p.first -= minY;
        p.second -= minX;
    }
}

퍼즐을 90도 회전시키는 함수입니다

// 00 01 02 03
// 10 11 12 13
// 20 21 22 23
// 30 31 32 33

// ->

// 30 20 10 00
// 31 21 11 01
// 32 22 12 02
// 33 23 13 03

// Max Y = 3
// nextY = MaxY - curX
// nextX = curY

// 00 -> (MaxY - curX)(curY) = 30
// 03 -> (MaxY - curX)(curY) = 00

회전할때의 규칙을 보고 코드를 만들었습니다.

 

전체 코드

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

using namespace std;

vector<vector<pair<int, int>>> puzzles;
vector<vector<pair<int, int>>> empties;
vector<vector<bool>> visited;

bool check(vector<vector<int>>& table, int y, int x, int n)
{
    return y >= 0 && y < table.size() && x >= 0 && x < table[0].size() && table[y][x] == n; 
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<pair<int, int>> bfs(vector<vector<int>>& table, int y, int x, int n)
{
    vector<pair<int, int>> ret;
    queue<pair<int, int>> q;
    q.push({y, x});
    visited[y][x] = true;
        
    int minY = y, minX = x;
    
    while (!q.empty())
    {
        auto [cy, cx] = q.front(); q.pop();
        ret.push_back({cy, cx});
        
        for (int i = 0; i < 4; i++)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (check(table, ny, nx, n) && !visited[ny][nx])
            {
                q.push({ny, nx});
                visited[ny][nx] = true;

                minY = min(minY, ny);
                minX = min(minX, nx);
            }
        }
    }
    
    
    for (pair<int, int>& p : ret)
    {
        p.first -= minY;
        p.second -= minX;
    }
    return ret;
}

void rot(vector<pair<int, int>>& v)
{
    int maxY = 0, minY = 100000, minX = 100000;
    for (auto& p : v)
        maxY = max(maxY, p.first);

    for (auto& p : v)
    {
        int temp = p.first;
        p.first = maxY - p.second;
        p.second = temp;
        
        minY = min(minY, p.first);
        minX = min(minX, p.second);
    }
    
    
    for (pair<int, int>& p : v)
    {
        p.first -= minY;
        p.second -= minX;
    }

  
}

bool match(vector<pair<int, int>>& puzzle, vector<pair<int, int>>& empty)
{
    if (puzzle.size() != empty.size())
        return false;

    for (int r = 0; r < 4; r++)
    {
        int cnt = 0;
        for (pair<int, int>& e : empty)
        {
            for(pair<int, int>& p : puzzle)
            {
                if (p == e){
                    cnt++;
                    break;                
                }
            }
        }
        
        if (cnt == puzzle.size())
            return true;

        rot(puzzle);
    }
    
    return false;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    
    visited.resize(table.size(), vector<bool>(table[0].size(), false));
    for (int i = 0; i < table.size(); i++){
        for (int j = 0; j < table[i].size(); j++){
            if (!visited[i][j] && table[i][j] == 1)
                puzzles.push_back(bfs(table, i, j, 1));
        }
    }
    
    visited.clear();
    visited.resize(game_board.size(), vector<bool>(game_board[0].size(), false));
    for (int i = 0; i < game_board.size(); i++){
        for (int j = 0; j < game_board[i].size(); j++){
            if (!visited[i][j] && game_board[i][j] == 0)
                empties.push_back(bfs(game_board, i, j, 0));
        }
    }
    
    vector<bool> used(puzzles.size(), false);
    
    int answer = 0;
    for (auto& empty : empties){
        for (int i = 0; i < puzzles.size(); i++)
        {
            if (!used[i] && match(puzzles[i], empty))
            {
                used[i] = true;
                answer += puzzles[i].size();
                break;
            }
        }
    }
    
    
    
    return answer;
}