[알고리즘]모노미도미노(삼성)

Developer:Bird·2021년 3월 18일
0

알고리즘

목록 보기
12/17

https://www.acmicpc.net/problem/19235

개인적으로 이문제가 지금까지 풀었던 모든 삼성문제중 가장 빡센 문제 였던것 같다.
이문제는 각종스킬 및 어려운 알고리즘을 요구하지 않는다. 즉 시간복잡도와 공간복잡도에 관한 고려를 하지 않고 완전 탐색에만 집중하면 된다. 단 기능구현에 있어 가장 중요한 각절차들이 실수하기가 쉬운만큼 꼼꼼하고 꼼꼼하게 고려 해야한다.

[절차]

  1. 막대를 내린다.(땅이나 다른 막대가 닿을때까지)
  2. 제거할 막대 라인이 있으면 제거한다.
  3. 제거된 막대라인으로 인해 떨어져야할 막대가 있을시 떨어트린다.(이때 하나의 막대는 분리되면 안된다.)
  4. (2~3)의 작업을 제거할 막대가 없을때까지 진행한다.
  5. 막대의 옅은 부분에5. 막대의 옅은 부분에 막대가 남아있으면 없을때까지 밑으로 내려준다.

[리팩토링 및 효율]

1. 보드 구현 처리

파란색 보드와 초록색 보드의 시뮬레이션 과정을 따로 구현하게 된다면 코드가 상당히 난잡해진다. 사실상 두 보드가 지원하는 기능은 동일하므로 하나의 함수내에서 처리하는게 좋다. 하나의 함수내에서 파란보드일때,초록보드일때를 나누어서 진행하여도 되지만 이또한 상당히 실수할 요소가 많아진다. 프로그래머는 실수할 요소가 많은 코드를 작성하면 안된다.(이것은 범죄) 즉 보드는 그대로 유지하되 떨어트리는 막대만 회전해서 떨어트리면 된다. 초록보드일때는 그냥 떨어트리고 파란 보드일때는 (x,y)->(y,x)회전 변환하자!

2. 함수로 쪼개기.(AOP)

모든 기능들에 대해서 함수로 나뉘게 되면 유지보수의 측면에서 좋지만 정해진 시간내에서 구현해야하는 입장에서 함수갯수도 많아지고 기능들에 대해 혼동이 올수 도 있다. 사실 어떤기능들을 함수로 빼서 쓰고 리팩토링할것 인지는 과학의 영역보다는 예술의 영역에 가깝다고 생각한다. 일반적으로 필자는 실수하기 쉽거나, 자주 쓰이거나, 역할이 명료하게 구분가능한 부분들에 대해 함수로 나누었다. 나눈 함수에 대해 살펴 보면 다음과 같다.

1.범위확인 함수
현재 막대가 범위 안에있는지 체크한다. 이러한 시뮬레이션과정에서 다음과 같이 범위확인을 하는작업이 상당히 빈번하다.

2.회전 함수
역할이 명료하다. 그린보드에서 사용했던걸 블루보드에도 사용하기 위해 막대를 회전시킨다. 함수로 만들지 않아도 되지만 코드를 전부 구현한후, 코드를 재검토할때 상당히 직관적이다.

3.막대 떨어뜨리는 함수
이 문제에서 막대는 계속적으로 떨어진다. 이부분은 전체 구현부분에서 큰부분을 차지하는데, 이러한 큰 로직덩어리는 분리시키는게 실수방지 하기에 좋다.

4.블록 합치기
막대를 떨어트릴때 붙어있는 막대도 같이 떨어트리기 위해 이기능을 구현하였다.
이기능도 적절한 코드블록사이즈를 가지고 있으며 역할이 명료하다.

[구현]

#include <bits/stdc++.h>
using namespace std;
#define Board vector<vector<int>>
struct Block
{
    int y, x;
};
int score = 0, number_blocks = 0;
Board green_board(6, vector<int>(4));
Board blue_board(6, vector<int>(4));
vector<vector<Block>> Blocks({{{0, 0}}, {{0, 0}}, {{0, 0}, {0, 1}}, {{0, 0}, {1, 0}}});
int N;
void rotate(vector<Block> &blocks) 
{
    for (auto &block : blocks)
        swap(block.y, block.x);
}
bool isRange(Board &board, vector<Block> blocks)
{
    for (auto &block : blocks)
    {
        if (block.y <= 5 && block.y >= 0 && block.x >= 0 && block.x <= 3 && board[block.y][block.x] == 0)
            continue;
        return false;
    }
    return true;
}
void down(int number, Board &board, vector<Block> blocks)
{
    for (auto &block : blocks)
        board[block.y][block.x] = 0;
    while (1)
    {
        vector<Block> next = blocks;
        for (auto &block : next)
            block.y += 1;
        if (isRange(board, next))
            swap(next, blocks);
        else
            break;
    }
    for (auto &block : blocks)
        board[block.y][block.x] = number;
}
vector<Block> comb_block(Board &board, int y, int x)
{
    vector<Block> blocks({{y, x}});
    int number = board[y][x];
    if (y >= 1 && board[y - 1][x] == number)
        blocks.push_back({y - 1, x});
    else if (y <= 1 && board[y + 1][x] == number)
        blocks.push_back({y + 1, x});
    else if (x <= 2 && board[y][x + 1] == number)
        blocks.push_back({y, x + 1});
    else if (x >= 1 && board[y][x - 1] == number)
        blocks.push_back({y, x - 1});
    return blocks;
}
void go(int number, Board &board, vector<Block> blocks)
{
    //  
    int rotate_y = 100; //평행이동지점
    for (auto &block : blocks)
        rotate_y = min(rotate_y, block.y);
    for (auto &block : blocks)
    {
        block.y -= rotate_y; //평행이동 및 board에 채워넣기
    }

    //2.막히는 지점이 나올때까지 떨어트리기
    down(number, board, blocks);
    int before = -1;
    //3.지울 수 있는걸 한번에 다 지우기 밑에서 부터 체크
    while (before != score)
    {
        before = score;
        for (int y = 0; y <=5; y++)
        {
            int line_length = 0;
            for (int x = 0; x <= 3; x++)
            {
                if (board[y][x] != 0)
                    line_length++;
            }
            if (line_length == 4) //full
            {
                for (int x = 0; x <= 3; x++)
                    board[y][x] = 0;
                score++;
            }
        }
        //4.이때 같은 블록은 같이 떨어져야함 //어떻게 체크하지
        for (int y = 5; y >= 0; y--)
            for (int x = 0; x <= 3; x++)
                if (board[y][x] != 0)
                    down(board[y][x], board, comb_block(board, y, x)); //같은블록은 합쳐서 한번에 내리기;
    }
    //5. 3->4의 작업을 지울 수 있는게 없을때까지 반복
    //6 옅은부분 체크
    int howManyDown = 0;
    for (int y = 0; y <= 1 && howManyDown == 0; y++)
    {
        for (int x = 0; x <= 3; x++)
        {
            if (board[y][x] != 0)
            {
                howManyDown = 2 - y;
                break;
            }
        }
    }
    if (howManyDown > 0)
    {
        //7 옅은부분 만큼 밑으로 내리기
        for (int y = 5; y >= howManyDown; y--)
        {
            for (int x = 0; x <= 3; x++)
            {
                board[y][x] = board[y - howManyDown][x];
            }
        }
        //옅은부분 지우기
        for (int y = howManyDown-1; y >= 0; y--)
        {
            for (int x = 0; x <= 3; x++)
                board[y][x] = 0;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    int num = 0;
    while (N-- > 0)
    {
        num++;
        int t, x, y;
        cin >> t >> y >> x;
        vector<Block> next = Blocks[t];
        for (auto &block : next)
        {
            block.y += y;
            block.x += x;
        }
        go(num, green_board, next); // 그린보드 작업
        rotate(next); ///블루보드에 넣기 위해 회전
        go(num, blue_board, next); //블루보드 작업
    }
    for (int y = 2; y <= 5; y++)
        for (int x = 0; x <= 3; x++)
        {
            if (green_board[y][x] != 0)
                number_blocks++;
            if (blue_board[y][x] != 0)
                number_blocks++;
        }
    cout << score << "\n" << number_blocks;
    return 0;
}
profile
끈임없이 발전하자.

0개의 댓글