99클럽 코테 스터디 7일차 TIL : 깊이/너비 우선탐색(DFS/BFS) - 퍼즐 조각 채우기 (챌린저)

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

오늘은 챌린저 문제도 풀어봤다!!

노가다로 푼것같지만,,, 일단 통과했다는거에 의의를 두고,,ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

거의 2~3시간 걸린것같다,, 더 빨리 풀 수 있었어야 했을것같은데

챌린저도 1시간 이내로 푸는걸 목표로 둬야겠다.

---

문제는 간단하다!

빈칸이 있는 game_board가 있고, 퍼즐조각이 있는 table이 주어진다.

table에 있는 퍼즐조각을 최대한 많이 game_board의 빈칸에 채우는 문제이다.

 

제약조건이 많아서 비교적 쉽게 풀었던것같다.

1. 퍼즐의 회전은 가능하지만 뒤집기는 불가능하다

2. 빈칸을 채울때 무조건 꽉 채워야한다! 퍼즐 두개를 이용해 채우거나, 빈칸이 남으면 안된다.

    특히 이 조건이 없어서 더 간단히 풀었던것같다... 이 조건도 있었으면 여러 조각을 합친모습까지 생각해야 했어서 머리가 터졌을지두,,,,,,,,

 

동작도 간단하다.

1. game_board에서 빈칸만 찾는다

2. table에서 퍼즐만 찾는다

3. 빈칸과 퍼즐조각을 비교하면서 채울 수 있는지를 확인한다.

 

빈칸찾기와 퍼즐찾기를 하나의 함수로 똑같이 해결했다. (find함수)

동작은 간단하다! 이걸 어떻게 DFS, BFS로 적용해야 하는지 몰라서 냅다 주어진 테이터를 전부 탐색하면서 진행하였다

일단 재귀를 써야해서 재귀함수의 이름을 BFS라 하긴 했는데,, 이게 맞는지는 모르겠다. 속도도 꽤나 느렸

 

[find]

0. empty를 찾는건지 block을 찾는건지 isempty라는 인자로 받아온다

    isempty가  true면 빈칸을 찾는것 == 즉 0인곳을 찾는것이므로 test를 0이라한다

    fals면 block을 찾는것 == 즉 1인곳을 찾는것이므로 test를 1이라한다

1. 배열을 처음부터 순차적으로 보면서 empty칸을 찾는다

2. empty칸을 찾으면 여기서부터 BFS를 시작

    -> BFS로 앞뒤양옆(대각선의 빈칸은 연결된걸로 안침) 빈칸을 전부 찾는다.

        이렇게 찾은 빈칸들은 (index i, indexj)형태의 벡터묶음(즉 2차원벡터)으로 받아온다.

        이때, 여기서 찾은 빈칸은 이미 찾은 빈칸이다. find에서 순차적으로 볼 때 나중에 있는 빈칸도 연결되어 같이 걸릴 수 있으므로 거기서 안걸리에 전부 채워준다! (여기서는 0이었던 배열의 값을 1로 바꿔줌)

3. BFS의 결과는 index 묶음형태이므로 비교하기 힘들다!

    table과 board_game이 주어진것처럼 2차원 배열에 모양인곳을 1로 채워주는 형식으로 바꿔준다.

    나중에 block이랑 empty랑 ==연산자로 비교할것이므로, empty를 찾을때도 그냥 1로 채워서 보내준다!

    어짜피 여기서부터는 그냥 empty모양들만 모아둔것이니까 판별만 되면 된다.

4. 결과를 리턴한다 (2차원 배열의 묶음이므로 3차원 배열(벡터))

 

[turn]

90도, 180도, 270도를 돌릴 수 있다.

근데 180, 270같은 경우에는 90을 2번 3번 한것이므로 turn90만 구현해서 여러번 돌려주는것으로 해결한다!

인덱스값 변화에 규칙이 있어서 이걸 사용했다. 기존이 (i,j)이고 이게 90도 돌아가면 (turni, turnj)가 된다고 할 때

1. 일단 90도 돌아간 결과물의 크기는 기존 block크기의 반대이다! row size와 column size가 반대인 배열을 새로 만들어준다.

2. turni : j를 그대로 사용한다 (돌아가는 거니까!)

    turnj : i의 반대이다! 

    a b c 순서로 증가하던 i, turn된 다음에는 c b a순서로 j가 증가한다!

 

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

using namespace std;

void BFS(vector<vector<int>> &board, vector<vector<int>> &result, bool isempty, int i, int j){
    // [i,j]를 시작으로 연결된 빈공간 (혹은 블럭)찾기!!
    // 연결은 앞뒤양옆 4가지 방향으로만 가능 -> i +-1, j+-1 4가지 케이스!
    // 이 때 index를 넘어가는 상황 방지를 해줘야함
    
    int test = 1;
    int nottest = 0;
    if(isempty){
        test = 0;
        nottest = 1;
    }
    //cout << "BFS (i, j, test) : " <<i<<", "<<j<<", "<<test<< endl;
    
    result.push_back({i,j}); // 일단 지금위치 추가
    board[i][j] = nottest; // 넘어온곳을 다시 검사하면 안되니까!
    
    // 빈칸인곳을 찾으면 다음스텝으로!
    if(i < board.size()-1 && board[i+1][j] == test){
        BFS(board, result, isempty, i+1, j);
    }
    if(i > 0 && board[i-1][j] == test){
        BFS(board, result, isempty, i-1, j);
    }
    if(j < board.size()-1 && board[i][j+1] == test){
        BFS(board, result, isempty, i, j+1);
    }
    if(j > 0 && board[i][j-1] == test){
        BFS(board, result, isempty, i, j-1);
    }
    // 앞뒤양옆으로 더이상 빈칸인곳이 없으면 탐색종료!
}

vector<vector<vector<int>>> find(vector<vector<int>> board, bool isempty){
    int test = 1;
    if(isempty){
        test = 0;
    }
    
    //cout << "start find" << endl;
    
    vector<vector<vector<int>>> result;
    int size = board.size();
    for(int i = 0; i<size; i++){
        for(int j = 0; j <size; j++){
            if(board[i][j] == test){
                vector<vector<int>> block;
                BFS(board, block, isempty, i, j); // empty or block 한개를 찾은것 -> index모음임!!
                //cout << "--------[find block!]------ "<<endl;
                
                
                int maxi=block[0][0];
                int mini=block[0][0];
                int maxj=block[0][1];
                int minj=block[0][1];
                
                for(int k = 0; k<block.size(); k++){
                    if(maxi < block[k][0]){
                        maxi = block[k][0];
                    }else if(mini > block[k][0]){
                        mini = block[k][0];
                    }
                    if(maxj < block[k][1]){
                        maxj = block[k][1];
                    }else if(minj > block[k][1]){
                        minj = block[k][1];
                    }
                }
                
                int sizej = maxj - minj + 1;
                int sizei = maxi - mini + 1;
                //cout << "mini, maxi : "<<mini<<", "<<maxi<<endl;
                //cout << "minj, maxj : "<<minj<<", "<<maxj<<endl;
                //cout << "sizej, sizei : "<<sizej<<", "<<sizei<<endl;
                
                vector<vector<int>> blockk(sizei, vector<int>(sizej));
                
                for(int k = 0; k<block.size(); k++){
                    int ki = block[k][0] - mini;
                    int kj = block[k][1] - minj;
                    blockk[ki][kj] = 1;
                }
                /*
                for(int a=0; a<sizei; a++){
                    for(int b=0; b<sizej; b++){
                        cout << blockk[a][b] <<" ";
                    }
                    cout<<endl;
                }
                */
                //cout <<"----------------------------- "<<endl;
                result.push_back(blockk);
            }
        }
    }
    return result;
}

vector<vector<int>> turn90(vector<vector<int>> block){
    int block_rows = block.size();
    int block_columns = block[0].size();
    //cout<<"block_row : "<<block_rows<<endl;
    //cout<<"block_columns : "<<block_columns<<endl;
    vector<vector<int>> block90(block_columns, vector<int>(block_rows));
    
    for(int i = 0; i<block_rows; i++){
        for(int j = 0; j<block_columns; j++){
            int turni = j;
            int turnj = block_rows-1 - i;
            
            //cout << "(i, j) : "<< i<<", "<<j<<endl;
            //cout << "(turni, turnj) : "<< turni<<", "<<turnj<<endl;
            block90[turni][turnj] = block[i][j];
        }
    }
    return block90;
}

vector<vector<int>> turn(vector<vector<int>> block, int option){
    // turn 해서 돌려주기 -> 90도, 180도, 270도 3가지 옵션이 있음
    // optiont 1 : 90, 2 : 180, 3 : 270
    //cout << "Start turn"<<endl;
    vector<vector<int>> result;
    
    switch(option){
        case 1 :
            result = turn90(block);
            break;
        case 2: 
            result = turn90(turn90(block));
            break;
        case 3 :
            result = turn90(turn90(turn90(block)));
            break;
    }
    
    
    return result;
}



int size(vector<vector<int>> block){
    
    int size = 0;
    for(int i = 0; i<block.size(); i++){
        for(int j = 0; j<block[0].size(); j++){
            if(block[i][j] == 1){
                size++;
            }
        }
    }
    return size;
}

void print_block(vector<vector<int>> block){
    for(int a=0; a<block.size(); a++){
                    for(int b=0; b<block[0].size(); b++){
                        cout << block[a][b] <<" ";
                    }
                    cout<<endl;
                }
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0;
    
    // 빈칸 찾기 (따로따로 하나의 2차원 배열로) <- 이게 DFS,BFS?? 어떻게,,,?
    vector<vector<vector<int>>> emptys = find(game_board, true);
    
    // 블럭 찾기 (따로따로 하나의 2차원 배열로)
    // 블럭의 경우 회전이 가능하다는점도 생각할것!
    vector<vector<vector<int>>> blocks = find(table, false);
    
    // 딱들어맞는지 확인
    for(int i = 0; i<emptys.size(); i++){
        int emptysize = size(emptys[i]);
        bool eraseflag = false;
        for(int j = 0; j<blocks.size(); j++){
            int blocksize = size(blocks[j]);
            if(emptysize == blocksize && !eraseflag){
                // 들어갈 가능성이 생김
                //cout << "[erase test]"<<endl;
                //cout << "block"<< endl;
                //print_block(blocks[j]);
                //cout << "empty"<<endl;
                //print_block(emptys[i]);
                if(emptys[i] == blocks[j]){
                    // 모양 그대로 들어갈 수 있음
                    //cout << "모양 그대로 삭제"<<endl;
                    //emptys.erase(emptys.begin()+i); // 지우기
                    blocks.erase(blocks.begin()+j);
                    answer += blocksize;
                    eraseflag = true;
                    continue;
                }else if(emptys[i] == turn(blocks[j], 1)){
                    // 90도 회전
                    //cout << "90"<<endl;
                    //emptys.erase(emptys.begin()+i); // 지우기
                    blocks.erase(blocks.begin()+j);
                    answer += blocksize;
                    eraseflag = true;
                    continue;
                }else if(emptys[i] == turn(blocks[j], 2)){
                    // 180
                    //cout << "180"<<endl;
                    //emptys.erase(emptys.begin()+i); // 지우기
                    blocks.erase(blocks.begin()+j);
                    answer += blocksize;
                    eraseflag = true;
                    continue;
                }else if(emptys[i] == turn(blocks[j], 3)){
                    // 270
                    //cout << "270"<<endl;
                    //emptys.erase(emptys.begin()+i); // 지우기
                    blocks.erase(blocks.begin()+j);
                    answer += blocksize;
                    eraseflag = true;
                    continue;
                }
                //cout<<"-----------------"<<endl;
            }
        }
    }
    
    return answer;
}

---

문제풀면서 이렇게 길게적은건 처음인거같은데.,,,

여러모로 삽질도 많이하고 딱히 효율적인 코드는 아닌것같다.

그치만,,, 챌린저 성공에 의의를 둬야겠다 하하!!