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

프로그래머스: 문제

코딩테스트 연습 - 3주차_퍼즐 조각 채우기

괜히 새로운 문제 찾는 것보다 이전에 풀었던 문제를 제대로 다시 풀어보는 게 중요한 것 같다.

특히 이러한 까다로운 2차원 배열 문제는 네이버 뿐만 아니라 삼성에도 (매우) 자주 출제되는 문제이고 어려운 테스트케이스에서 덤벙대는 나에게 좋은 훈련의 기회가 된다.

 

문제 쟁점

game_board의 빈칸에 table의 퍼즐 블록을 끼워넣는다. 

→ 빈칸, 퍼즐 블록탐색을 어떻게 알아낼까?

→ 상하좌우로 퍼즐이 인접해있는 경우가 없다고 한다. 물론 빈칸도 붙어있으면 하나의 블록 처리 한다.

→ DFS로 탐색해나가면서 다른 값을 만나기 전까지의 범위로 구역을 나눈다.

→ 최대한 많은 빈칸을 채운다. 이것이 최종 목표!

 

퍼즐은 회전할 수 있다.

→ 방법은 크게 두 가지

1. 퍼즐을 돌린다.

2. 보드판 자체를 돌린다.

둘 중 하나의 방식을 택해서 정방향, 90도회전, 180도 회전, 270도 회전으로 총 4방향으로 모두 탐색해봐야한다는 뜻

 

문제 풀이

여기서는 문제를 편리하게 풀기 위해서 몇 가지 장치를 택했다.

1. 구조체 사용

x좌표와 y좌표를 명확히 파악함으로써 혼란을 줄이기 위해 별도의 구조체를 사용하였다.

 

2. 문제 풀이의 중심을 구해야한다.

우선 board의 빈칸을 중심으로 탐색하였고 빈칸에 알맞는 퍼즐 블록을 table에서 가져온다. 그리고 그 블록을 사용하면 table에는 0으로 표시하여 퍼즐 없앰 처리 한다. 이러한 과정을 game_board를 완전 탐색할 때까지 반복한다.

 

3. 괜히 메모리 아낀다고 고생하지 말자. 

배열 몇 개 복사한다고 효율성에 문제 안 생긴다. 예외 처리 힘들게 하는 거보다 간단 명료하게 배열 복사해서 꼬이는 일을 방지하는 게 훨씬 낫다.

 

4. 비슷한 역할을 하는 코드는 최대한 한 데 모으자

만약 비슷한 코드를 두 세 개 작성하면 매번 디버깅하고 고치기 번거롭더라. type으로 나누어서 처리하고, 최대한 함수화해서 묶는 게 효율적이고 실수도 최소화할 수 있다.

 

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int b[50][50], visited_board[50][50] = {0};
int t[50][50], visited_table[50][50] = {0};
int dx[] = {-1, 1, 0 , 0};
int dy[] = {0, 0, -1, 1};
int s = 0;
struct point {
    int x;
    int y;
};
vector<point> bv, tv;
int flag = 0;
int answer = 0;

void rotate();
bool cmp(const point& a, const point& b);
int check();
void DFS(int x, int y, int main_x, int main_y, int cnt, int type);
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    s = game_board.size();
    // copy
    for(int i = 0;i < s;i++){
        for (int j = 0; j < s;j++){
            b[i][j] = game_board[i][j];
            t[i][j] = table[i][j];
        }
    }
    //board의 빈칸을 중심으로 탐색
    for(int i = 0;i < s;i++){
        for(int j = 0;j < s;j++){
            // 방문하지 않은 빈 칸
            if(!visited_board[i][j] && !game_board[i][j]) {
                bv.clear();
                flag = 0;
                DFS(j, i, j, i, 1, 1);
                if(!flag){
                    for(int k = 0;k < 4;k++){
                        int c = check();
                        if(c) break;
                        rotate();
                    }
                }
            }
        }
    }
    return answer;
}


void rotate() {
    int temp[50][50];
    memcpy(temp, t, sizeof(t));
    // for(int k = 0;k < s / 2;k++) {
        // 여기서 i, j는 temp의 행, 열 indexing
    int k = 0;
    for(int i = k;i < s - s / 2;i++){
        for(int j = k;j < s - s / 2;j++){
            // up
            t[j][i] = temp[s - 1 - i][j];
            // right
            t[j][s - 1 - i] = temp[i][j];
            // left
            t[s - 1 - j][i] = temp[s - 1 - i][s - 1 - j];
            // down
            t[s - 1 - j][s - 1 - i] = temp[i][s - 1 - j];
        }
    }
    // }
}

bool cmp(const point& a, const point& b){
    if (a.x < b.x) return true;
    if (a.x == b.x){
        if(a.y < b.y) return true;
        else return false;
    }
    else return false;
}

int check() {
    memset(visited_table, 0, sizeof(visited_table));
    for(int i = 0;i < s;i++){
        for(int j = 0;j < s;j++){
            if(!visited_table[i][j] && t[i][j]){
                tv.clear();
                DFS(j,i,j,i,1, 2);
                if(tv.size() == bv.size()){
                    sort(tv.begin(), tv.end(), cmp);
                    sort(bv.begin(), bv.end(), cmp);

                    int tflag = 0;
                    for(int k = 0;k < tv.size();k++){
                        if(bv[k].x == tv[k].x && bv[k].y == tv[k].y) continue;
                        else {
                            tflag = 1;
                            break;
                        }
                    }
                    if (tflag) continue;

                    for(int k = 0;k < tv.size();k++) {
                        // vector에는 상대적 위치가 아니라 절대적 위치가 저장되기 때문
                        // 활용할 때는 다시 절대적 시작점 더해줘야 한다.
                        int nx = j + tv[k].x;
                        int ny = i + tv[k].y;
                        t[ny][nx] = 0;
                        answer++;
                    }
                    // 퍼즐 맞추기 성공
                    return 1;
                }
            }
        }
    }
    return 0;
}

void DFS(int x, int y, int main_x, int main_y, int cnt, int type) {
    // board 탐색은 type = 1, table 탐색은 type = 2
    if (type == 1){
        bv.push_back({x - main_x, y - main_y});
        visited_board[y][x] = 1;
    }
    else {
        tv.push_back({x - main_x, y - main_y});
        visited_table[y][x] = 1;
    }
    if(cnt > 6){
        // 퍼즐조각은 최대 6개
        flag = 1;
        return;
    }
    
    for(int i = 0; i < 4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx > -1 && nx < s && ny > -1 && ny < s){
            if(type == 1 &&  !visited_board[ny][nx] && !b[ny][nx]){
                DFS(nx, ny, main_x, main_y, cnt + 1, type);
            }
            else if (type == 2 && !visited_table[ny][nx] && t[ny][nx]) {
                DFS(nx, ny, main_x, main_y, cnt + 1, type);
                if(flag) return;
            }
        }
    }
}