퍼즐 조각 채우기

문제

https://programmers.co.kr/learn/courses/30/lessons/84021?language=cpp 

코딩테스트 연습 - 3주차

---

접근방법

1) 접근 사고

game_board와 table의 위치들을 파싱해준뒤 각  도형의 위치들을 비교해주면서 일치할 경우 도형을 지워주고 도형의 수치값만큼 더해주는 방식으로 문제를 해결했습니다.

제 실력으로는 구현을 하던 도중에 막혀서

https://blog.naver.com/jinhan814/222474893356

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

블로그의 코드를 참조해서 풀었습니다. 구조체에 역할을 각각 분할해서 구현한 코드라서 객체지향적인 코드인거 같습니다.

코드마다 주석을 자세하게 적었습니다.

2) 시간 복잡도

n의 크기가 작으므로 n^2으로도 해결이 가능했습니다.

3) 배운 점

구현할 때 처음에 저는 도형의 좌표를 다 적어서 무식하게 구현하려고 했었는데 117번재 줄을 보면 최소 최대 좌표를 구해서 도형의 필요한 경우만 구해준뒤 도형을 돌리는 형식으로 비교해주는 방식을 사용하면 좀 더 효율적인거 같습니다. 이런 구현을 배운건 정말 운이 좋았던거 같습니다.

4) PS

새로운 구현 코드를 볼 수 있어서 너무 좋았습니다.

 

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
constexpr int INF = 1e9 + 7;
 
int moveY[] ={0,1,0,-1};
int moveX[] ={1,0,-1,0};
struct Block{
    int n, m;
    vector<vector<int>> v;
    Block(int n, int m) : n(n), m(m), v(n, vector<int>(m)) {}
 
    Block Rotate(){
        Block ret(m, n);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                ret[j][n -1 - i] = v[i][j];
            return ret;
    }
 
    int GetCnt() const{
        int ret = 0;
        for (vector<int> i : v)
            ret += reduce(i.begin(), i.end()); // 도형의 전체 값들을 반환하는 과정
        return ret;
    }
 
    friend bool operator == (const Block& a, const Block& b)
    {
        if (a.GetCnt() != b.GetCnt())
            return 0;
        Block t = a;
        for(int i = 0; i < 4; i++)
        {
            if(t.n == b.n && t.m == b.m && t.v == b.v) //블럭 하나당 비교해주는 과정, 블럭의 y축 x축이 같고 Block의 값이 같다면
                {
//디버깅 과정
//                for(int i = 0; i < t.n; i++)
//                {
//                    for(int j = 0 ; j < t.m; j++)
//                    {
//                        cout << t.v[i][j] <<" ";
//                    }
//                    cout<<"\n";
//                }
//                cout <<"--------------------" << "\n";
//                for(int i = 0; i < b.n; i++)
//                {
//                    for(int j = 0 ; j < b.m; j++)
//                    {
//                        cout << b.v[i][j] <<" ";
//                    }
//                    cout<<"\n";
//                }
//                cout <<"=====================" <<"\n";
                return 1;
            }
            t = t.Rotate();
        }
        return 0;
    }
 
    vector<int>& operator[] (int i) { return v[i];}
};
 
vector<Block> Extract(vector<vector<int>> board, bool flag)
{
    //Flag는 밑에서 BFS탐색을 할 때 visited 역할을 한다.
    vector<Block> ret;
    int n = board.size(); //board의 y축
    int m = board[0].size();//board의 x출
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(board[i][j] != flag) //탐색해야 하는 경우가 아니라면 continue!
                continue;
            vector<pii> v; //나중에 반환해줄 도형 배열에 값을 체크해주기 위한 vector
            queue<pii> Q;// BFS탐색을 위한 queue
 
            //밑에서 반환해줄 2차원 도형의 배열값 맨 좌측 상단 위치와 맨 우측 하단 값을 구한뒤 서로 좌표를 빼주면 도형의 전체크기가 나옴
            //114줄을 보면 이해하기 쉽다.
            int x_mn = INF, x_mx = -INF;
            int y_mn = INF, y_mx = -INF;
 
            v.push_back({i, j});
            Q.push({i, j});
            board[i][j] = !flag;
            while(Q.size())
            {
                auto[x, y] = Q.front();
                Q.pop();
                x_mn = min(x_mn, x),x_mx = max(x_mx, x);
                y_mn = min(y_mn, y),y_mx = max(y_mx, y);
 
                for(int d = 0; d < 4; d++)
                {
                    int nextX = x + moveX[d];
                    int nextY = y + moveY[d];
                    if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m)
                        continue;
                    if(board[nextX][nextY] != flag)
                        continue;
                    v.push_back({nextX, nextY});
                    Q.push({nextX, nextY});
                    board[nextX][nextY] = !flag;
                }
            }
 
            //반한해줄 도형을 의미하는 2차원 배열에 값들을 체크한뒤 반환하는 과정
            Block cur(x_mx - x_mn + 1, y_mx - y_mn + 1);
            for (auto &[x, y] : v)
                cur[x - x_mn][y - y_mn] = 1;
            ret.push_back(cur);
        }
    return ret;
}
int solution(vector<vector<int>> game_board, vector<vector<int>> table)
{
    int ret = 0;
    // Block 구조체는 사실상 2차원 배열이다.
    // v1는 문제에서 주어지는 game_board 배열에서 도형을 둘 수 있는 자리를 저장하는 vector이다.
    // v2는 문제에서 주어지는 table 배열에서 도형의 크기와 인덱스값들을 저장하는 vector이다.
    vector<Block> v1 = Extract(game_board, 0);
    vector<Block> v2 = Extract(table, 1);
    for(Block& i : v1)
    {
        for(int j = 0; j < v2.size(); j++)
        {
            //v1과 v2를 비교하면서 v2 도형과 v1의 테이블 위치가 일치하다면 v2를 지워준다. 그리고 그만큼 수치는 결과값에 저장한다.
            if(i == v2[j])
            {
                ret += i.GetCnt();
                v2.erase(v2.begin() + j);
                break;
            }
        }
    }
    return ret;
}
 
using board = vector<vector<int>>;
board game_board = {
        { 1, 1, 0, 0, 1, 0 },
        { 0, 0, 1, 0, 1, 0 },
        { 0, 1, 1, 0, 0, 1 },
        { 1, 1, 0, 1, 1, 1 },
        { 1, 0, 0, 0, 1, 0 },
        { 0, 1, 1, 1, 0, 0 },
        };
board table = {
        { 1, 0, 0, 1, 1, 0 },
        { 1, 0, 1, 0, 1, 0 },
        { 0, 1, 1, 0, 1, 1 },
        { 0, 0, 1, 0, 0, 0 },
        { 1, 1, 0, 1, 1, 0 },
        { 0, 1, 0, 0, 0, 0 },
        };
 
int main(void)
{
    fastio;
    cout << solution(game_board, table) << '\n';
}
 

복습

 

#include<bits/stdc++.h>
 
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X, Y) make_pair(X,Y)
#define mt(X, Y) make_tuple(X,Y)
#define mtt(X, Y, Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
int moveY[] = {0, -1, 0, 1};
int moveX[] = {1, 0, -1, 0};
 
struct block {
    int n, m;
    vector<vector<int>> board;
 
    block(int n, int m) : n(n), m(m), board(n, vector<int>(m)) {}
 
    block Rotate() {
        block ret(m, n); 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                ret[j][n - i - 1] = board[i][j];
            return ret;
    }
 
    int getSum() {
        int ret = 0;
        for (int i = 0; i < board.size(); i++)
            ret += reduce(board[i].begin(), board[i].end());
        return ret;
    }
 
    friend bool operator == (block &a, block &b)
    {
        if(a.getSum() != b.getSum())
            return 0;
        block t = a;
        for(int i = 0; i < 4; i++)
        {
            if(t.m == b.m && t.n == b.n && t.board == b.board)
                return 1;
 
            t = t.Rotate();
        }
        return 0;
    }
 
    vector<int> &operator[] (int i) { return board[i]; }
};
 
vector<block> Extract(vector<vector<int>> board, int flag) {
    vector<block> ret;
    int n = board.size();
    int m = board[0].size();
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (board[i][j] != flag)
                continue;
 
            vector<pii > v;
            queue<pii > q;
            v.push_back({i, j});
            q.push({i, j});
            board[i][j] = !flag;
            int y_mx = INT_MIN, y_mn = INT_MAX;
            int x_mx = INT_MIN, x_mn = INT_MAX;
 
            while (q.size()) {
                int y = q.front().first;
                int x = q.front().second;
                q.pop();
 
                y_mx = max(y_mx, y), y_mn = min(y_mn, y);
                x_mx = max(x_mx, x), x_mn = min(x_mn, x);
 
                for (int d = 0; d < 4; d++) {
                    int ny = y + moveY[d];
                    int nx = x + moveX[d];
 
                    if(ny < 0 || ny >= n || nx < 0 || nx >= m)
                        continue;
                    if(board[ny][nx] != flag)
                        continue;
 
                    v.push_back({ny, nx});
                    q.push({ny, nx});
                    board[ny][nx] = !flag;
                }
            }
 
            block cur(y_mx - y_mn + 1, x_mx - x_mn + 1);
            for(int i = 0; i < v.size(); i++)
                cur[v[i].first - y_mn][v[i].second - x_mn] = 1;
            ret.push_back(cur);
        }
    return ret;
}
 
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int ret = 0;
    vector<block> v1 = Extract(game_board, 0);
    vector<block> v2 = Extract(table, 1);
 
    for(block& b : v1)
        for(int j = 0; j < v2.size(); j++)
        {
            if(b == v2[j])
            {
                ret += b.getSum();
                v2.erase(v2.begin() + j);
                break;
            }
        }
    return ret;
}
 
using board = vector<vector<int>>;
board game_board = {
        { 1, 1, 0, 0, 1, 0 },
        { 0, 0, 1, 0, 1, 0 },
        { 0, 1, 1, 0, 0, 1 },
        { 1, 1, 0, 1, 1, 1 },
        { 1, 0, 0, 0, 1, 0 },
        { 0, 1, 1, 1, 0, 0 },
        };
board table = {
        { 1, 0, 0, 1, 1, 0 },
        { 1, 0, 1, 0, 1, 0 },
        { 0, 1, 1, 0, 1, 1 },
        { 0, 0, 1, 0, 0, 0 },
        { 1, 1, 0, 1, 1, 0 },
        { 0, 1, 0, 0, 0, 0 },
        };
 
int main(void)
{
    fastio;
    cout << solution(game_board, table) << '\n';
}