[2019 KAKAO BLIND RECRUITMENT] 블록 게임(C++)

https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

 

오랜만에 한 번만에 끝낸 문제!

접근법 공유해드립니다.

 

---

 

코드를 바로 작성하기 전에 문제를 파악하고 어떻게 풀어야 할까를 먼저 생각해봐야 한다. 이 문제는 절대 시뮬레이션 문제가 아니다!

 

---

 

우선, 문제를 살펴보자!

하나의 모형은 4개의 블럭으로 구성되어 있다. 4개로 이루어진 블록들중에서도, 없앨 수 있는 블록은 5가지가 존재한다.

5가지 모형에 대해서 표현해보겠다.

 

 

 

1. ___|

 

2. |___

 

3. ㅗ

 

4. |_

 

5. _|

 

 

이 5가지가 미래에(?) 없애질 가능성이 있는 놈들이다. 

 

 

 

우선 모든 블록 조합들을 파악하기 위해서, vector<pair<int,int>> v[201]의 자료구조에 모든 블록조합을 넣는다. 1 ~ 200까지 자연수로 이루어졌으므로, 201을 설정했다.

 

 

 

 

이제 이 자료구조를 모두 탐색하며, 미래에 없애질 놈들을 찾아서 새로운 자료구조에 넣어야 한다.

1번 모형(___|) 에 대해서 생각해보면, 가장 꼭대기에 있는 애가 0번째 원소가 될 것이고, 아래부터 차례로 1,2,3번을 구성할 것이다. 이 순서는, board 자료구조를 읽는 방식에 의해서 설정된 것이다.

 

 

 

 

 

1,2,3번 블록들은 행 인덱스가 동일해야 하고, 각 열은 1씩 차이로 구성되어야 한다. 0번과 1번 블록은 열 인덱스가 같아야 하고 행은 1차이가 나야 한다.

 

 

이 것을 코드로 구현하면 다음과 같다. 이런 식으로 2, 3, 4, 5번 모형에 대해서도 구현해야 하면 된다.

 

        // |___ : Type 1
        if (b_v[i][1].first == b_v[i][2].first && b_v[i][2].first == b_v[i][3].first
            && b_v[i][1].second + 1 == b_v[i][2].second && b_v[i][2].second + 1 && b_v[i][3].second
            && b_v[i][0].first + 1 == b_v[i][1].first && b_v[i][0].second == b_v[i][1].second) {
 
        }

 

 

---

 

자, 이제 미래에 없어질 후보들이 진짜 없어질지에 대해서 확인해야 한다. 블록이 없어지기 위해서는 검은 블록을 이용해 꽉 찬 직사각형을 만들어야 한다.

 

 

검은 블록이 해당 블록으로 안전하게(?) 내려올 수 있어야 없어질 수 있다. 따라서, 안전하게 내려올 수 있는지를 확인해줘야 한다.

 

 

확인하는 것은 반복문을 통해서 쉽게 확인할 수 있다.

 

 

삭제될 수 있는 블록들의 인덱스를 저장해두고 후보들에서 일괄적으로 삭제하고, 배열에서도 0으로 표시해야 한다.

다시 후보들중에서 사라질 수 있는 것들을 탐색해야 한다.

 

 

이 과정을 반복하면 쉽게 문제를 해결할 수 있다.

 

 

---

 

추가적으로, 코드 구현에는 문제가 없지만 Segmentation Error가 발생할 수 있다. 나도 같은 에러를 겪었는데, 이유는 블록들을 구성하는 숫자가 1~N(N<=200)까지 연속적으로 발생한다고 착각을 했기 때문이다. 이 부분을 염두하고 코드를 수정한다면, 쉽게 통과할 수 있을 것이다.

 

 

---

코드구현(C++)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
 
using namespace std;
 
int solution(vector<vector<int>> board) {
    int answer = 0;
    vector<vector<int>> copy(board);
    vector<pair<int, int>> b_v[201];
    set<pair<int, int>> s;
    int length = 0;
    for (int i = 0; i < copy.size(); i++) {
        for (int j = 0; j < copy[i].size(); j++) {
            if (copy[i][j] != 0) {
                b_v[copy[i][j]].push_back(make_pair(i, j));
                length = max(length, copy[i][j]);
            }
        }
    }
 
    // Find
    for (int i = 1; i <= length; i++) {
        if (b_v[i].size() == 0)
            continue;
        // |___ : Type 1
        if (b_v[i][1].first == b_v[i][2].first && b_v[i][2].first == b_v[i][3].first
            && b_v[i][1].second + 1 == b_v[i][2].second && b_v[i][2].second + 1 && b_v[i][3].second
            && b_v[i][0].first + 1 == b_v[i][1].first && b_v[i][0].second == b_v[i][1].second) {
            s.insert(make_pair(i, 1));
        }
        // ___| : Type 2
        else if (b_v[i][1].first == b_v[i][2].first && b_v[i][2].first == b_v[i][3].first
            && b_v[i][1].second + 1 == b_v[i][2].second && b_v[i][2].second + 1 && b_v[i][3].second
            && b_v[i][0].first + 1 == b_v[i][3].first && b_v[i][0].second == b_v[i][3].second) {
            s.insert(make_pair(i, 2));
        }
        // ㅗ : Type 3
        else if (b_v[i][1].first == b_v[i][2].first && b_v[i][2].first == b_v[i][3].first
            && b_v[i][1].second + 1 == b_v[i][2].second && b_v[i][2].second + 1 && b_v[i][3].second
            && b_v[i][0].first + 1 == b_v[i][2].first && b_v[i][0].second == b_v[i][2].second) {
            s.insert(make_pair(i, 3));
        }
        // |_ : Type 4
        else if (b_v[i][0].first + 1 == b_v[i][1].first && b_v[i][1].first + 1 == b_v[i][2].first
            && b_v[i][0].second == b_v[i][1].second && b_v[i][1].second == b_v[i][2].second
            && b_v[i][3].first == b_v[i][2].first && b_v[i][2].second + 1 == b_v[i][3].second) {
            s.insert(make_pair(i, 4));
        }
        // _| : Type 5
        else if (b_v[i][0].first + 1 == b_v[i][1].first && b_v[i][1].first + 1 == b_v[i][3].first
            && b_v[i][0].second == b_v[i][1].second && b_v[i][1].second == b_v[i][3].second
            && b_v[i][2].first == b_v[i][3].first && b_v[i][2].second + 1 == b_v[i][3].second) {
            s.insert(make_pair(i, 5));
        }
    }
 
    // While Check
    while (s.size() != 0) {
        vector<pair<int, int>> d_v;
        for (set<pair<int, int>>::iterator it = s.begin(); it != s.end(); it++) {
            int idx = (*it).first;
            int type = (*it).second;
            // |___ : Type 1
            if (type == 1) {
                int row = b_v[idx][2].first - 1;
                int col1 = b_v[idx][2].second;
                int col2 = b_v[idx][3].second;
                while (row >= 0) {
                    if (copy[row][col1] == 0 && copy[row][col2] == 0) {
                        row--;
                        if (row == -1) {
                            d_v.push_back(make_pair(idx, type));
                            break;
                        }
                    }
                    else
                        break;
                }
            }
            // ___| : Type 2
            else if (type == 2) {
                int row = b_v[idx][1].first - 1;
                int col1 = b_v[idx][1].second;
                int col2 = b_v[idx][2].second;
                while (row >= 0) {
                    if (copy[row][col1] == 0 && copy[row][col2] == 0) {
                        row--;
                        if (row == -1) {
                            d_v.push_back(make_pair(idx, type));
                            break;
                        }
                    }
                    else
                        break;
                }
            }
            // ㅗ : Type 3
            else if (type == 3) {
                int row = b_v[idx][1].first - 1;
                int col1 = b_v[idx][1].second;
                int col2 = b_v[idx][3].second;
                while (row >= 0) {
                    if (copy[row][col1] == 0 && copy[row][col2] == 0) {
                        row--;
                        if (row == -1) {
                            d_v.push_back(make_pair(idx, type));
                            break;
                        }
                    }
                    else
                        break;
                }
            }
            // |_ : Type 4
            else if (type == 4) {
                int row = b_v[idx][3].first - 1;
                int col1 = b_v[idx][3].second;
                while (row >= 0) {
                    if (copy[row][col1] == 0) {
                        row--;
                        if (row == -1) {
                            d_v.push_back(make_pair(idx, type));
                            break;
                        }
                    }
                    else
                        break;
                }
            }
            // _| : Type 5
            else {
                int row = b_v[idx][2].first - 1;
                int col1 = b_v[idx][2].second;
                while (row >= 0) {
                    if (copy[row][col1] == 0) {
                        row--;
                        if (row == -1) {
                            d_v.push_back(make_pair(idx, type));
                            break;
                        }
                    }
                    else
                        break;
                }
            }
        }
 
        // Deleting
        if (d_v.size() == 0)
            break;
        else {
            answer += d_v.size();
            for (int i = 0; i < d_v.size(); i++) {
                for (int j = 0; j < 4; j++)
                    copy[b_v[d_v[i].first][j].first][b_v[d_v[i].first][j].second] = 0;
                s.erase(d_v.at(i));
            }
        }
    }
 
    return answer;
}