ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [프로그래머스] - 퍼즐 조각 채우기 c++
    알고리즘/프로그래머스 2022. 2. 4. 10:34
    728x90
    반응형

    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

    댓글

Designed by Tistory.