적절히 객체화를 잘 하면 비교적 간결하게 구현할 수 있는 구현문제.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

/*

1. 0과 1로 채워진 2차원 격자판 두 개가 입력으로 들어오며, 각각은 다음 의미를 갖는다.
   game_board: 빈칸(0)과 채워진 칸(1)으로 이루어진 격자판.
   table: table 배열의 1은 블록을 의미하고 0은 빈칸을 의미한다. 1은 상하좌우로 둘 이상
          인접할 수 있으며, 이 경우 1이 인접한 모양대로 table에 블록이 놓여있음을 뜻한다.
          table에 블록은 둘 이상 있을 수 있다.
   
   이 문제는, table에 놓여있는 블록을 인식하여, game_board의 빈칸에 딱 맞도록 채워넣기로 할 때,
   game_board의 빈칸이 최대 몇 칸이나 채워질 지 구하는 문제다.
   (단, game_board의 빈칸에 블록을 채워넣을 땐 game_board에 블록을 놓은 후 그 블록의
    상하좌우 인접한 칸에는 빈칸이 있어서는 안 된다.)


2. 다음과 같은 알고리즘으로 코드를 구현했다.
   (1) game_board의 빈칸과 table의 블록을, 각각을 구성하는 좌표들을 원소로 한 배열로 인식하여
       BLOCK이라는 클래스형의 blanks라는 이름과 blocks라는 이름의 배열에 각각 넣는다.
       즉, blanks[0]는 game_board에서 인식한 빈칸이 저장되고
           blocks[0]는 table에서 인식한 블록이 저장된다.
   (2) blanks[i]와 blocks[j]가 일치하는지 검토 후, 일치하면 answer 값을 증가시키고
       blocks 배열에서 blocks[j] 원소를 삭제한다.
       일치하지 않는다면 blocks[j]를 시계방향으로 1/4바퀴 회전시킨 후 다시 비교한다.
       일치하지 않는다면 반 바퀴, 3/4바퀴 회전시킨 후 다시 비교한다.
   (3) answer를 출력한다.


3. 전체적인 로직은 간결하나 세부적인 함수와 메소드의 구현이 다소 복잡한 점이 많은 코드였다.
   빈칸/블록을 (r, c) 여러개로 구성된 배열로 추출하는 단계가 필요하다는 점, 그리고
   빈칸과 블록의 일치여부 판단은 (r, c) 형태에서 2차원 배열 형태로 변환 후 하는 것이
   간편하다는 점을 인식해 이에 따라 코드를 구현하면 구현이 간결해진다는 점을 아는 게 중요했다.
   특히 game_board와 table에서 빈칸/블록을 인식해내는 부분은 크기가 늘어나는 이차원배열을 
   리턴값으로 하는 DFS를 구현해야 했기에 실수할 수 있는 부분이 많았는데, 
   C++ STL의 vector 컨테이너의 insert 함수를 이용해 상당히 간결하게 이를 구현할 수 있었다.
*/


#include <vector>

using namespace std;
int N;

class BLOCK{
    private:
    vector<pair<int, int>> pos;
    
    public:
    BLOCK(vector<pair<int, int>> pos) { this->pos = pos; }
    vector<vector<int>> get_status()
    {
        int min_r = N, min_c = N;
        int size_r = 0, size_c = 0;
        for (auto [r, c] : this->pos)
        {
            min_r = min(min_r, r); min_c = min(min_c, c);
            size_r = max(size_r, r); size_c = max(size_c, c);
        }
        vector<vector<int>> status(size_r-min_r+1, vector<int>(size_c-min_c+1));
        for (auto [r, c] : this->pos)
            status[r-min_r][c-min_c] = 1;
        return status;
    }
    void turn()
    {
        vector<pair<int, int>> b;
        for (auto [r, c] : this->pos)
            b.push_back({c, N-r-1});
        this->pos = b;
    }
    int get_size() { return this->pos.size(); }
};



vector<pair<int, int>> get_block(int r, int c, int sw, vector<vector<int>> &board)
{
    int dr[4] = {0, 0, 1, -1};
    int dc[4] = {1, -1, 0, 0};
    vector<pair<int, int>> a(1, {r, c});
    board[r][c] = 1-sw;
    for (int i=0; i<4; i++)
    {
        int nr = r + dr[i], nc = c + dc[i];
        if (nr == N || nr < 0 || nc == N || nc < 0 || board[nr][nc] != sw)
            continue;
        vector<pair<int, int>> b = get_block(nr, nc, sw, board);
        a.insert(a.end(), b.begin(), b.end());
    }
    return a;
}


bool is_same_block(vector<vector<int>> a, vector<vector<int>> b)
{
    if (a.size() != b.size() || a[0].size() != b[0].size()) return false;
    for(int j=0; j<a.size(); j++)
        for(int k=0; k<a[0].size(); k++)
            if (a[j][k] != b[j][k]) return false;
    return true;
}

bool fit_into_blank(BLOCK block, BLOCK blank)
{
    for (int i=0; i<4; i++, block.turn())
        if (is_same_block(blank.get_status(), block.get_status())) 
            return false;
    return true;
}


int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0; N = game_board.size();
    vector<BLOCK> blanks, blocks;
    
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
        {
            if (game_board[i][j] == 0)
                blanks.push_back(get_block(i,j,0,game_board));
            if (table[i][j] == 1)
                blocks.push_back(get_block(i,j,1,table));
        }
    
    for (auto blank : blanks)
        for (int l = 0; l < blocks.size(); l++)
            if (fit_into_blank(blocks[l], blank))
            {
                answer += blank.get_size();
                blocks.erase(blocks.begin()+l);
                break;
            }
    return answer;
}