-
[프로그래머스] - 퍼즐 조각 채우기 c++알고리즘/프로그래머스 2022. 2. 4. 10:34728x90반응형
https://programmers.co.kr/learn/courses/30/lessons/84021
코딩테스트 연습 - 퍼즐 조각 채우기
[[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]] [[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]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0
programmers.co.kr
해당 문제를 푸는 데 많은 시간이 들었다.
푸는 방식은 감이 왔지만, 알고리즘을 조금 오랜만에 풀어서 그런가..? 막상 구현을 하는 데 시간이 좀 걸렸다..
내가 초반에 착각했던 점은,
'최대'로 채울 수 있는 조각 칸의 갯수이니까, 이 경우의 수가 여러개인 줄 알았다. 그 여러 경우의 수 중 '최대'를 출력하는 건 줄 알았던 것이다...! 하지만, 보드가 0인 곳에 꼭 맞는 조각은 table 에서 정해져 있다. 같은 위치에 여러가지 table조각이 들어갈 수 있는 것이 아니기 때문에(물론 같은 모양의 조각이 table에 여러개가 있을 수 있지만, 상관없다), 그냥 해당 위치가 가능하다면 채우고 answer에 조각 칸의 수만큼 더해주면, 끝이었다.
로직은 다음과 같다.
1. 우선 dfs로 table 을 순회하며 1인 곳의 좌표를 저장한 2차원 vector 조각모음을 만들어 준다.
2. game_board를 90 도 만큼 회전시켜 좌표를 갱신한다.
(x, y) -> (y, -x)
3. 해당 game_board를 가지고, 1에서 저장한 조각모음들과 하나씩 비교한다. 조각이 들어갈 수 있는가?
1이 갖고있는 조각모음 중 하나를 가지고 설명하자면,
조각의 좌표를 움직여 game_board의 처음부터(0, 0,) 끝까지(n, n) 훑으며 해당 조각이 들어갈 수 있는 자리인지 검사한다. game_board의 해당 칸이 0이면 cnt 를 증가시키고, cnt가 조각의 칸 수와 같다면, 조각의 칸 하나하나를 순회하며 상하좌우가 0이 아닌지 검사한다. 만약 0이라면, 조각과 모양이 꼭 맞지 않는 것이므로, answer에 추가되지 않는다.
만약 꼭 맞는다면 answer에 조각 칸 수만큼 추가되고, 조각모음 visit 배열을 만들어 해당 조각은 다음에 사용하지 않도록 하며, game_board에도 1로 만들어 다음에 해당 칸에 또 조각을 끼워맞추지 않도록 한다.
완성된 코드는 다음과 같다.
1.
void dfs(int y, int x, int n, vector<pair<int,int>> &block, vector<vector<int>> &table) { if(visited[y][x]) return; if(table[y][x] == 0) return; visited[y][x] = 1; block.push_back({ y, x }); for(int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue; dfs(ny, nx, n, block, table); } }
2.
int solution(vector<vector<int>> game_board, vector<vector<int>> table) { int answer = 0; int n = table.size(); for(int i = 0; i < table.size(); i++) { for(int j = 0; j < table[0].size(); j++) { if(table[i][j] == 1) { vector<pair<int,int>> block; dfs(i, j, table.size(), block, table); if(block.size()) allPairs.push_back(block); } } } vector<vector<int>> rotateBoard(n, vector<int>(n,0)); vector<bool> pairsVis(allPairs.size(), false); for(int rot = 0; rot < 4; rot++) { // rotate for(int r = 0; r < n; r++) { for(int c = 0; c < n; c++) { rotateBoard[r][c] = game_board[c][n-r-1]; } } for(int i = 0; i < allPairs.size(); i++) { if(pairsVis[i] == 0 && solve(rotateBoard, allPairs[i])) { answer += allPairs[i].size(); pairsVis[i] = 1; } } // rotate for(int r = 0; r < n; r++) { for(int c = 0; c < n; c++) { game_board[r][c] = rotateBoard[r][c]; } } } return answer; }
3.
bool solve(vector<vector<int>> &board, vector<pair<int,int>> block) { int n = board.size(); for(int r = -n + 1; r < n; r++) { for(int c = -n + 1; c < n; c++) { vector<pair<int,int>> fitblock; for(auto b : block) fitblock.push_back({b.first + r, b.second + c}); int cnt = 0; for(int i = 0; i < fitblock.size(); i++) { pair<int,int> cur = fitblock[i]; if(cur.first < 0 || cur.second < 0 || cur.first >= n || cur.second >= n) break; if(board[cur.first][cur.second] == 1) break; cnt++; } if(cnt == fitblock.size()) { bool fit = true; for(auto a : fitblock) board[a.first][a.second] = 1; for(int i = 0; i < fitblock.size(); i++) { pair<int,int> cur = fitblock[i]; for(int d = 0; d < 4; d++) { int ny = cur.first + dy[d]; int nx = cur.second + dx[d]; if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue; if(board[ny][nx] == 0) { fit = false; break; } } if(fit == false) break; } if(fit == false) { for(auto a : fitblock) board[a.first][a.second] = 0; } else { return true; } } } } return false; }
완성된 코드는 다음과 같다.
#include <string> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <cstring> using namespace std; int visited[51][51]; int dy[] = {-1, 1, 0, 0}; int dx[] = {0, 0, -1, 1}; vector<vector<pair<int,int>>> allPairs; void dfs(int y, int x, int n, vector<pair<int,int>> &block, vector<vector<int>> &table) { if(visited[y][x]) return; if(table[y][x] == 0) return; visited[y][x] = 1; block.push_back({ y, x }); for(int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue; dfs(ny, nx, n, block, table); } } bool solve(vector<vector<int>> &board, vector<pair<int,int>> block) { int n = board.size(); for(int r = -n + 1; r < n; r++) { for(int c = -n + 1; c < n; c++) { vector<pair<int,int>> fitblock; for(auto b : block) fitblock.push_back({b.first + r, b.second + c}); int cnt = 0; for(int i = 0; i < fitblock.size(); i++) { pair<int,int> cur = fitblock[i]; if(cur.first < 0 || cur.second < 0 || cur.first >= n || cur.second >= n) break; if(board[cur.first][cur.second] == 1) break; cnt++; } if(cnt == fitblock.size()) { bool fit = true; for(auto a : fitblock) board[a.first][a.second] = 1; for(int i = 0; i < fitblock.size(); i++) { pair<int,int> cur = fitblock[i]; for(int d = 0; d < 4; d++) { int ny = cur.first + dy[d]; int nx = cur.second + dx[d]; if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue; if(board[ny][nx] == 0) { fit = false; break; } } if(fit == false) break; } if(fit == false) { for(auto a : fitblock) board[a.first][a.second] = 0; } else { return true; } } } } return false; } int solution(vector<vector<int>> game_board, vector<vector<int>> table) { int answer = 0; int n = table.size(); for(int i = 0; i < table.size(); i++) { for(int j = 0; j < table[0].size(); j++) { if(table[i][j] == 1) { vector<pair<int,int>> block; dfs(i, j, table.size(), block, table); if(block.size()) allPairs.push_back(block); } } } vector<vector<int>> rotateBoard(n, vector<int>(n,0)); vector<bool> pairsVis(allPairs.size(), false); for(int rot = 0; rot < 4; rot++) { // rotate for(int r = 0; r < n; r++) { for(int c = 0; c < n; c++) { rotateBoard[r][c] = game_board[c][n-r-1]; } } for(int i = 0; i < allPairs.size(); i++) { if(pairsVis[i] == 0 && solve(rotateBoard, allPairs[i])) { answer += allPairs[i].size(); pairsVis[i] = 1; } } // rotate for(int r = 0; r < n; r++) { for(int c = 0; c < n; c++) { game_board[r][c] = rotateBoard[r][c]; } } } return answer; } int main() { vector<vector<int>> 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 } }; vector<vector<int>> 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 result = solution(game_board, table); printf("%d\n", result); }
728x90'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 자물쇠와 열쇠 C++ (0) 2022.02.10