[programmers] 퍼즐 조각 채우기

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

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dfs

 

---------------------------------------------------풀이----------------------------------------------------

 

간단하게 모든 경우에 대해 계산하는 문제이다.

 

먼저, table 벡터를 전부 탐색하면서 방문하지 않은 퍼즐 조각의 일부(table[x][y]==1)를 발견하면 put_to_board() 함수로 넘어간다.

 

put_to_board()에서는 전체 game board를 돌면서 퍼즐이 들어갈 수 있는 위치를 찾는다.

game_board[i][j]가 0, 즉 들어갈 공간이 존재할 경우, can_put()함수를 통해 딱 맞게 들어가는지 체크한다.

만약 딱 맞다면, game_board[i][j]와 연결된 0인 부분을 전부 1로 채워 퍼즐을 채운 것으로 만들고,

table[x][y]와 연결된 1인 부분을 전부 0으로 채워 퍼즐을 방문한 것으로(없앤 것으로) 표시한 후 그 퍼즐의 크기를 리턴한다.

-> fill_board()함수 이용

만약 퍼즐을 채울 수 있는 곳이 없다면, 퍼즐을 방문한 것으로 표시 후 0을 리턴한다. -> 들어갈 수 있는 위치가 없으므로 없애준것.

 

can_put() 함수에서는 rotate()함수를 통해 table 배열을 오른쪽으로 90도씩 회전시킨다.

x,y(회전 전 원래 상태에서의 퍼즐위치가 x,y. 따라서 회전 시마다 변경 필요.)에 해당하는 퍼즐에 대해

90도씩 회전한 상태로 game_board에 적용해보는 단계이다.

네 방향 중 하나라도 해당하는게 있는지 찾기 위해 or를 사용하여 결과를 bool type으로 리턴하였다.

이 과정은 is_match()함수로 행해진다.

 

is_match() 함수는 i,j에 해당하는 game board의 빈 칸들과 x,y에 해당하는 table에서의 퍼즐이 정확히 일치하는지를 체크해 리턴한다.

여기서 dfs를 활용하였는데,

i,j와 x,y에서 똑같이 상하좌우를 매번 체크하면서

game board가 비어있는 칸이면 table의 퍼즐이 존재하는 칸이어야하고,

game board가 채워져있거나 갈 수 없으면, table의 퍼즐이 존재하지 않거나 갈 수 없는 칸이어야 한다.

따라서 갈 수 있는 부분에 대해 상하좌우를 매번 체크하는 방식이고,

위 조건에 따라 전부 맞으면 true를 리턴한다.

#include <string>
#include <vector>
#include <cstdlib>
#include <iostream>

using namespace std;

int dx[4] = {0, 0, -1 ,1};
int dy[4] = {-1, 1, 0, 0};
vector<vector<int>> game_board, table;
bool visited[51][51] = {false, };

// x,y에서 시작해서 prev값인 부분을 fill로 채움.
// 채운 개수만큼 리턴
int fill_board(vector<vector<int>> &board, int x, int y, int prev, int fill){
    int num = 1;
    board[x][y] = fill;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= board.size() || ny < 0 || ny >= board.size() || board[nx][ny] != prev){
            continue;
        }
        num += fill_board(board, nx, ny, prev, fill);
    }
    return num;
}

// 90도 방향으로 회전
void rotate(){
    vector<vector<int>> tmp_table = table;
    for(int i = 0; i < table.size(); i++){
        for(int j = 0; j < table.size(); j++){
            table[j][table.size()-i-1] = tmp_table[i][j];
        }
    }
}

// 퍼즐 모양에 맞게 게임보드 빈칸을 확인하면서 
// 보드에 빈칸이 남지 않게 채울 수 있는지 체크
bool is_match(int x1, int y1, int x2, int y2){
    bool ans = (game_board[x1][y1] == 0) && (game_board[x1][y1] ^ table[x2][y2]);
    if(!ans){
        return ans;
    }
    visited[x2][y2] = true;
    for(int i = 0; i < 4; i++){
        int nx1 = x1 + dx[i];
        int ny1 = y1 + dy[i];
        int nx2 = x2 + dx[i];
        int ny2 = y2 + dy[i];
        if(nx1 < 0 || nx1 >= game_board.size() || ny1 < 0 || ny1 >= game_board.size() || game_board[nx1][ny1]){
            if(nx2 < 0 || nx2 >= table.size() || ny2 < 0 || ny2 >= table.size() || visited[nx2][ny2] || !table[nx2][ny2]){
                continue;
            }
            else{
                ans &= false;
                break; 
            }
        }
        else{
            if(nx2 < 0 || nx2 >= table.size() || ny2 < 0 || ny2 >= table.size() || !table[nx2][ny2]){
                ans &= false;
                break;
            }
            else if(visited[nx2][ny2]){
                continue;
            }
            else{
                // 퍼즐의 다음 부분 체크
                ans &= is_match(nx1, ny1, nx2, ny2);
            }
        }    
    }
    visited[x2][y2] = false;
    return ans;
}

bool can_put(int x1, int y1, int x2, int y2){
    bool ans = false;
    // 90도로 회전시키면서 체크
    for(int rot = 0; rot < 4; rot++){
        rotate();
        int tmp = x2;
        x2 = y2;
        y2 = table.size()-tmp-1;
        ans |= is_match(x1, y1, x2, y2);
    }
    return ans;
}

// x,y에 존재하는 퍼즐 조각을 보드에 맞춰봄.
// 맞출 수 있다면 거기에 넣고 퍼즐도 없애고, 보드도 채워줌.
// 맞출 수 없다면 퍼즐만 없애줌.
// 채워진 퍼즐 조각의 크기를 리턴.
int put_to_board(int x, int y){
    int size = 0;
    for(int i = 0; i < game_board.size(); i++){
        for(int j = 0; j < game_board.size(); j++){
            // 각 공간에 들어갈 수 있는지 체크
            if(!game_board[i][j] && can_put(i,j,x,y)){
                // 들어갈 수 있으면, 그리고 빈공간이 없으면
                // 퍼즐과 보드 정리
                size = fill_board(game_board, i, j, 0, 1);
                fill_board(table, x, y, 1, 0);
                return size;
            }
        }
    }
    // 넣을 수 없는 퍼즐.
    fill_board(table, x, y, 1, 0);
    return size;
}

// 총 채울 수 있는 칸수=?
int solution(vector<vector<int>> _game_board, vector<vector<int>> _table) {
    int answer = 0;
    game_board = _game_board; table = _table;
    
    for(int i = 0; i < table.size(); i++){
        for(int j = 0; j < table[i].size(); j++){
            // table에 올려진, 방문하지 않은 조각을 발견하면 
            if(table[i][j]){
                // 게임보드에 끼워맞춰봄
                // 되면 -> 보드까지 채우기 & 퍼즐 없애기 & 퍼즐 개수 리턴.
                // 안되면 -> 퍼즐 없애기
                answer += put_to_board(i, j);
            }
        }
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

사실 삼성 코테 문제 준비할때를 생각하면, 이정도는 1시간 컷이었겠으나,,

그동안 준비 안 한 대가를 치루는 중인듯.

진짜 dfs 짜는게 오래걸렸다! 디버깅도.....

반성해야겠다ㅠㅠ