[Programmers] 위클리 챌린지 3주차 - 퍼즐 조각 채우기

안녕하세요. 이번 포스팅에서는 프로그래머스 위클리 챌린지 3주 차 퍼즐 조각 채우기 문제를 풀어보도록 하겠습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차

 

해당 문제는 위 링크에서 도전해보실 수 있습니다.

 

 

이 문제를 풀기 위해서

우선 table의 조각들을 구분해야 합니다. 저는 각각 퍼즐을 vector<int>로 저장하였고, 이 조각들을 vector<vector<int>>에 넣어서 보관하였습니다.

 

간단하게 table에서 원소가 1이라면, dfs를 하여 갈수있는 칸들을 모두 vector에 담고, 방문 배열 처리를 합니다. 이렇게 모든 테이블 원소에 대해 dfs를 수행하게 되면 모든 조각들을 구할 수 있습니다.

 

모든 조각들을 구하였다면, 이제 game_board를 회전하면서 (-n+1, -n+1) ~ (n, n) 까지 배열을 평행이동하여 딱 맞는 조각이 있는지 확인합니다.

 

이런 식으로 배열을 평행이동하며 확인하는데, 배열이 회전으로 가지는 경우가 총 네 개이므로, 전체 포문을 네 번 돌리면서, 회전을 하고 각 회전 배열에 대해 수행해주시면 됩니다.

 

직관적으로 이해하기 쉽게 평행이동을 배열을 시킨다고 말씀드렸지만, 실제 코드에서는 가운데있는 조각을 평행이동시켜서 배열에 맞는지를 확인하였습니다.

 

 

그리고 조각의 수만큼 방문 배열을 선언하여, 한번 사용된 조각은 더이상 사용되지 않게 하였습니다.

 

추가로 조각이 들어갈 수 있는데, 조각이 맞춰졌음에도, 남는 칸이 있는지를 확인하기 위해서, 조각이 들어간 자리를 우선 1로 배열을 바꾸어 놓고, 조각의 좌표에서 동 서 남 북으로 확인하여 0이 있으면 다시 0으로 롤백해주었습니다. 0이 없다면 조각이 딱 들어맞았다는 의미이므로 현재 조각의 방문처리를 하였고, 결과에 조각의 개수를 추가해 주었습니다.

 

<소스 코드>

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

using namespace std;

int visited[51][51];
const int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,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+dir[i][0], nx = x+dir[i][1];
        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+dir[d][0], nx = cur.second+dir[d][1];
                        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;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.