Game Develop

[Algorithm] Programmers :: 퍼즐 조각 채우기 본문

Algorithm/Programmers

[Algorithm] Programmers :: 퍼즐 조각 채우기

MaxLevel 2022. 7. 31. 15:32

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
vector<vector<int>> gDir = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
struct Node
{
    int y;
    int x;
 
    Node(int _y, int _x) : y(_y), x(_x) {};
};
 
struct BoardDirNode
{
    vector<pair<int, int>> tilePositions; // 첫번째 인덱스 기준, 오,왼,오,오 담을거.
    int offsetX = 0;
    int tileCount;
    int matrixSize;
 
    BoardDirNode() {};
    BoardDirNode(vector<pair<int, int>> _tilePositions) : tilePositions(_tilePositions) {};
};
 
struct TableNode
{
    vector<pair<int, int>> tilePositions;
    int offsetX = 0;
    int tileCount;
    int matrixSize;
    bool isUsed = false;
};
 
vector<vector<int>> rotateMatrix(vector<vector<int>>& matrix, int matrixSize)
{
    vector<vector<int>> result(matrixSize, vector<int>(matrixSize, 0));
 
    // 90도 회전.
 
    for (int i = 0; i < matrixSize; i++)
    {
        for (int j = 0; j < matrixSize; j++)
        {
            result[j][matrixSize - i - 1] = matrix[i][j];
        }
    }
 
    for (int i = 0; i < matrixSize - 1; i++)
    {
        bool check = false;
        int zeroCount = 0;
 
        for (int i = 0; i < matrixSize; i++)
        {
            if (result[i][0] == 0) zeroCount++;
            else check = true;
        }
        if (check) break;
 
        // 퍼즐을 좌측상단쪽으로 몰아넣기. (딱 붙여넣는다는 말)
        // 위의 코드로 회전만 시킬 경우 좌측상단쪽에 몰아서 배치가 되지 않는다.
        // 땡겨주기 위해서 회전 후, 0번째 열부터 검사를 한다. 해당 열이 전부 0,즉 비어있는 공간이면 오른쪽 열을 땡겨온다.
 
        if (zeroCount == matrixSize) 
        {
            for (int r = 0; r < matrixSize; r++)
            {
                for (int c = 0; c < matrixSize - 1; c++)
                {
                    result[r][c] = result[r][c + 1];
                    result[r][c + 1] = 0;
                }
            }
        }
    }
    
    return result;
}
 
bool checkPuzzlePiece(BoardDirNode bdn, TableNode tn)
{
    vector<vector<int>> bdnMatrix(bdn.matrixSize, vector<int>(bdn.matrixSize, 0));
    vector<vector<int>> tnMatrix(tn.matrixSize, vector<int>(tn.matrixSize, 0));
 
    // 보드판 퍼즐을 매트릭스에 배치.
    for (int i = 0; i < bdn.tilePositions.size(); i++)
    {
        bdnMatrix[bdn.tilePositions[i].first][bdn.tilePositions[i].second] = 1;
    }
 
    // 테이블 퍼즐을 매트릭스에 배치.
    for (int i = 0; i < tn.tilePositions.size(); i++)
    {
        tnMatrix[tn.tilePositions[i].first][tn.tilePositions[i].second] = 1;
    }
 
    int checkCount = bdn.matrixSize * bdn.matrixSize;
 
    for (int i = 0; i < 4; i++)
    {
        int count = 0;
 
        for (int r = 0; r < bdn.matrixSize; r++)
        {
            for (int c = 0; c < bdn.matrixSize; c++)
            {
                if (bdnMatrix[r][c] == tnMatrix[r][c]) count++;
            }
        }
 
        if (count == checkCount) return true;
        tnMatrix = rotateMatrix(tnMatrix, tn.matrixSize); // 불일치 시, 90도 회전.
    }
 
    return false;
}
 
 
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
 
    int answer = 0;
    int maxBoardSize = game_board.size();
 
    vector<BoardDirNode> bdns;
    vector<TableNode> tns;
 
    for (int i = 0; i < game_board.size(); i++)
    {
        for (int j = 0; j < game_board[i].size(); j++)
        {
            if (game_board[i][j]) continue; // 1이면 리턴. 
 
            queue<Node> q;
            BoardDirNode bdn;
            q.push(Node(i, j));
            int tileCount = 1;
            int startY = i;
            int startX = j;
 
            int maxHeight = i; // 고정값. 무조건 첫번째 인덱스부터 시작해서 탐색하니까.
            int minHeight = i; // 타일중 i값 제일 높은거
            int minWidth = j; // 타일중 j값 제일 낮은거
            int maxWidth = j; // 타일중 j값 제일 높은거.
 
            bdn.debugIndex = make_pair(i, j);
            bdn.tilePositions.push_back(make_pair(i, j));
            game_board[i][j] = 1;
 
            while (!q.empty())
            {
                Node popedNode = q.front();
                q.pop();
 
                int currentY = popedNode.y;
                int currentX = popedNode.x;
 
                for (int i = 0; i < 4; i++)
                {
                    int nextY = currentY + gDir[i][0];
                    int nextX = currentX + gDir[i][1];
 
                    if (nextY < 0 || nextY > maxBoardSize - 1) continue;
                    if (nextX < 0 || nextX > maxBoardSize - 1) continue;
                    if (game_board[nextY][nextX]) continue;
 
                    game_board[nextY][nextX] = 1;
 
                    if (nextY > minHeight) minHeight = nextY; 
                    if (nextX < minWidth) minWidth = nextX; 
                    if (nextX > maxWidth) maxWidth = nextX; 
 
                    q.push(Node(nextY, nextX));
                    bdn.tilePositions.push_back(make_pair(nextY, nextX));
                    tileCount++;
                }
            } // 하나의 도형에 대한 탐색 종료.
 
            int matrixHeight = minHeight - maxHeight + 1;
            int matrixWidth = maxWidth - minWidth + 1;
 
            bdn.matrixSize = max(abs(matrixHeight), abs(matrixWidth)); // 매트릭스크기.
            bdn.tileCount = tileCount;
 
            int offsetX = minWidth;
            int offsetY = startY; 
 
            for (int i = 0; i < bdn.tilePositions.size(); i++)
            {
                bdn.tilePositions[i].first = bdn.tilePositions[i].first - offsetY;
                bdn.tilePositions[i].second = bdn.tilePositions[i].second - offsetX;
            }
 
            bdns.push_back(bdn);
        }
    }
 
    for (int i = 0; i < table.size(); i++)
    {
        for (int j = 0; j < table[i].size(); j++)
        {
            if (!table[i][j]) continue; // 0이면 리턴. 
 
            queue<Node> q;
            TableNode tn;
            q.push(Node(i, j));
            int tileCount = 1;
            int startY = i;
            int startX = j;
 
            int maxHeight = i; // 고정값. 무조건 첫번째 인덱스부터 시작해서 탐색하니까.
            int minHeight = i; // 타일중 i값 제일 높은거
            int minWidth = j; // 타일중 j값 제일 낮은거
            int maxWidth = j; // 타일중 j값 제일 높은거.
 
            tn.tilePositions.push_back(make_pair(i, j));
            table[i][j] = 0;
 
            while (!q.empty())
            {
                Node popedNode = q.front();
                q.pop();
 
                int currentY = popedNode.y;
                int currentX = popedNode.x;
 
                for (int i = 0; i < 4; i++)
                {
                    int nextY = currentY + gDir[i][0];
                    int nextX = currentX + gDir[i][1];
 
                    if (nextY < 0 || nextY > maxBoardSize - 1) continue;
                    if (nextX < 0 || nextX > maxBoardSize - 1) continue;
                    if (!table[nextY][nextX]) continue;
 
                    table[nextY][nextX] = 0;
 
                    if (nextY > minHeight) minHeight = nextY; 
                    if (nextX < minWidth) minWidth = nextX; 
                    if (nextX > maxWidth) maxWidth = nextX; 
 
                    q.push(Node(nextY, nextX));
                    tn.tilePositions.push_back(make_pair(nextY, nextX));
                    tileCount++;
                }
            } // 하나의 도형에 대한 탐색 종료.
 
            int matrixHeight = minHeight - maxHeight + 1;
            int matrixWidth = maxWidth - minWidth + 1;
 
            tn.matrixSize = max(abs(matrixHeight), abs(matrixWidth)); // 매트릭스크기.
            tn.tileCount = tileCount;
 
            int offsetX = minWidth;
            int offsetY = startY; // 고정. 
 
// offset값을 빼줌으로써 좌측상단으로 끌어당기기
            for (int i = 0; i < tn.tilePositions.size(); i++)
            {
                tn.tilePositions[i].first = tn.tilePositions[i].first - offsetY;
                tn.tilePositions[i].second = tn.tilePositions[i].second - offsetX;
            }
 
            tns.push_back(tn);
        }
    }
 
    for (int i = 0; i < bdns.size(); i++)
    {
        for (int j = 0; j < tns.size(); j++)
        {
            if (tns[j].isUsed) continue; // 이미 사용한 테이블블럭은 제외.
            if (!(bdns[i].tileCount == tns[j].tileCount)) continue; // 타일개수가 다르면 제외.
            if (!(bdns[i].matrixSize == tns[j].matrixSize)) continue; // 매트릭스크기가 다르면 제외.
 
            bool isFitted = false;
 
            isFitted = checkPuzzlePiece(bdns[i], tns[j]);
 
            if (isFitted)
            {
                tns[j].isUsed = true;
                answer += tns[j].tileCount;
                break;
            }
        }
    }
 
    return answer;
}
 cs
 
 
  

 

카카오 3레벨짜리 문젠데, 일반 3레벨짜리보다는 좀 더 어려운 문제였다.

일단 기본적으로 BFS,DFS 이용한 기본적인 탐색정도는 할 줄 알아야 한다.

도형의모양을 탐색을 통해 가져와서 비교를 해야하는데, 비교를 하기위해 거치는 전처리과정이 중요했던 것 같다.

 

먼저 보드판과 테이블에서 퍼즐들의 형태를 따와야한다.

그리고 따오는걸 어떤 형태로 저장을 할것인지가 중요하다. 왜냐하면 비교를 통해 맞는지 안맞는지 체크를 해야하기 때문이다.

그래서 형태를 따올 때 새로운 2차원배열에 좌측상단으로 끌어당긴 형태로 저장했다. 즉 0,0기준으로 끌어당긴 것이다.

이게 무슨말이냐면 0번째 행과 0번째 열에는 반드시 최소 1개의 타일이 있다는 것이다.

그래서 보드판이든 테이블이든 퍼즐을 0,0기준의 2차원배열에 저장했다. 배열의 크기는 n*n이며 n은 퍼즐의 높이와 너비중 큰값으로 했다. (정사각형의 형태) 굳이 크기를 더 크게할필요는 없기 때문이다. 필요 이상으로 크게 할 경우, 테이블의 퍼즐개수가 많을 경우 많은 메모리를 잡아먹는다.

 

그리고 실제 비교를 하기전에 몇가지 조건을 걸어 불필요한 검사를 줄였다.

이미 사용한 테이블의 퍼즐일 경우, 타일개수가 다를 경우, 매트릭스크기가 다를 경우이다.

퍼즐이 동일하면 타일개수와 매트릭스크기는 다를수가 없다.

비교는 각 행열의 원소의 일치하는 개수가 행열의 크기와 같으면 일치한다.

일치하지 않을경우 90도 회전한다. 그리고 다시 검사한다. 90도 회전코드는 따로 구글링을 해서 가져온 코드다.

90도 회전 시킨 후 검사를 하기전에 0,0쪽으로 끌어당겨야 한다. 

퍼즐모양에 따라 회전시켰을 때 0,0쪽으로 딱 붙어서 회전되지 않는 경우가 있다. 확인해본 결과 회전시킬 경우 위쪽으로는 딱 붙어서 나오는데 왼쪽에는 안붙게 회전되는 경우가 있다.

그렇기 때문에 0번째부터 열검사를 통해 해당 열이 전부 0이면(빈 타일이면) 해당열+1번째의 타일을 끌어서 가져온다.

열에 하나라도 1이 나올때까지 반복하면 된다.

그러면 회전후에도 비교가 가능한형태의 행렬이 완성된다. 그러면 끝이다.

 

이제보니 코드가 굉장히 긴데, 아마 줄이려면 더 줄일수는 있을것이다. 저렇게 짠 이유는 중간에 헷갈리지 않기위해 일일이 명시한 지역변수들이 많기도하고.. 사실 이 문제를 풀 때 바로 이렇게 푼게 아니라 삽질을 좀 많이하고 푼거다 보니까 도저히 더 건드릴 힘이 없었다. 뭔가 풀었다는거에 만족해버린 문제다.

 

 

 

 

'Algorithm > Programmers' 카테고리의 다른 글

[Algorithm] Programmers :: 캐시  (0) 2022.08.25
[Algorithm] Programmers :: 행렬 테두리 회전하기  (0) 2022.08.03
[Algorithm] Programmers :: 추석트래픽  (0) 2022.07.16
[Algorithm] Programmers :: 카카오프렌즈 컬러링북  (0) 2022.07.16
[Algorithm] Programmers :: 오픈채팅방  (0) 2022.07.15
'Algorithm/Programmers' Related Articles more