[프로그래머스] - 퍼즐 조각 채우기 c++

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

코딩테스트 연습 - 퍼즐 조각 채우기

 

해당 문제를 푸는 데 많은 시간이 들었다.

푸는 방식은 감이 왔지만, 알고리즘을 조금 오랜만에 풀어서 그런가..? 막상 구현을 하는 데 시간이 좀 걸렸다..

 

내가 초반에 착각했던 점은,

 

'최대'로 채울 수 있는 조각 칸의 갯수이니까, 이 경우의 수가 여러개인 줄 알았다. 그 여러 경우의 수 중 '최대'를 출력하는 건 줄 알았던 것이다...! 하지만, 보드가 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);
}