[TIL]24.04.19 알고리즘, 기타

1. 알고리즘 문제 해결

 

인공지능 테트리스 (Large) (백준 14599):

 핵심은 시뮬레이션 구현이었고, 그 내부에서 BFS/DFS나 그리디 등을 사용할 수 있는 문제였다. 아무래도 구현이 주가 되는 문제이다 보니 로직 자체는 심플하다. 대신에 세심하게 체크하지 않으면 놓치기 쉬운 부분이 많다. 나도 그래서 3번 정도의 시행착오를 거쳐야 했다.

 로직은 문제 그대로 구현하면 된다. 각 종류별 테트로미노들이 회전 없이 내려갈 때, 테트로미노 하나만을 이용해 제거할 수 있는 최대 줄 수를 구하면 된다.

 

 나 같은 경우에는, 먼저 테트로미노들을 표현할 수 있게 각각의 회전케이스들을 포함해 미리 구현했다. 한 점을 기준으로 테트로미노를 가장 좌측 상단 구석까지 당겨 붙인다고 생각한 뒤에, 테트로미노를 구성하는 모든 칸에 대해 기준점으로부터의 {y축 차이, x축 차이}를 vector로 저장했다. 이렇게 만들면 각 테트로미노 별로 1개~4개의 케이스(모양 및 회전에 따라)를 가지게 된다.

 그리고 이렇게 만들어진 모든 테트로미노 상태들에 대해서, BFS를 돌렸다. 기준점이 있다면, 위에서 만든 값을 이용해 실제 테트로미노들이 어느 칸에 들어갈지 알 수 있다. 따라서 (0,0)에서 시작해 BFS를 돌려, 갈 수 있는 모든 칸을 탐색하기 시작한다. 이때, 특정 지점에 배치한 테트로미노가 유효한지 판단한다(모든 칸이 게임판 위 빈칸에 놓이는 경우).

 만약 유효하다면 테트로미노가 더 내려갈 수 있는지 판단해서, 더 내려갈 수 없다면 그 시점에 제거되는 줄 수를 계산해서 최대 제거 줄 수를 최신화한다. 더 내려갈 수 있다면 테트로미노가 최종적으로 멈춘 상태가 아니므로, 제거 줄 수를 계산하지 않는다. 그리고나서 왼쪽, 오른쪽, 아래 방향의 기준점 대해 BFS를 마저 진행한다.

 BFS가 끝나면 최종적으로 제거될 수 있는 최대 줄 수를 얻을 수 있게 된다.

 

 나는 3번의 시행착오가 있었는데, 첫 번째는 내려오는 테트로미노가 회전 뿐 아니라 수평이동 조차 하지 않는다고 멋대로 생각했다가 틀렸다. 두 번째는 테트로미노가 더 내려갈 수 있는 상황임에도 제거 줄 수를 계산하도록 하는 바람에 틀렸다. 마지막으로는 배열 탐색 범위 디테일을 놓친 부분이 있어 틀렸다.

 아무래도 이것저것 구현할 게 많다보니, 집중하지 않으면 놓치기 쉬운 부분이 많았던 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef vector<pair<int, int> > minoState;
typedef vector<minoState> minoStateList;

minoStateList JMino { 
    { {0, 0}, {0, 1}, {1, 0}, {2, 0} },
    { {0, 0}, {0, 1}, {0, 2}, {1, 2} },
    { {0, 1}, {1, 1}, {2, 0}, {2, 1} },
    { {0, 0}, {1, 0}, {1, 1}, {1, 2} }
};

minoStateList LMino { 
    { {0, 0}, {0, 1}, {1, 1}, {2, 1} },
    { {0, 2}, {1, 0}, {1, 1}, {1, 2} },
    { {0, 0}, {1, 0}, {2, 0}, {2, 1} },
    { {0, 0}, {0, 1}, {0, 2}, {1, 0} }
};

minoStateList SMino { 
    { {0, 0}, {1, 0}, {1, 1}, {2, 1} },
    { {0, 1}, {0, 2}, {1, 0}, {1, 1} }
};

minoStateList ZMino { 
    { {0, 1}, {1, 0}, {1, 1}, {2, 0} },
    { {0, 0}, {0, 1}, {1, 1}, {1, 2} }
};

minoStateList TMino { 
    { {0, 0}, {1, 0}, {1, 1}, {2, 0} },
    { {0, 0}, {0, 1}, {0, 2}, {1, 1} },
    { {0, 1}, {1, 0}, {1, 1}, {2, 1} },
    { {0, 1}, {1, 0}, {1, 1}, {1, 2} }
};

minoStateList IMino { 
    { {0, 0}, {1, 0}, {2, 0}, {3, 0} },
    { {0, 0}, {0, 1}, {0, 2}, {0, 3} },
};

minoStateList OMino { 
    { {0, 0}, {0, 1}, {1, 0}, {1, 1} },
};

int dy[4] = {0, 1, 0};
int dx[4] = {1, 0, -1};
bool matrix[20][10];

int checkRemoveRowNum() {
    int result = 0;
    for(int i=0; i<20; i++) {
        bool flag = true;
        for(int j=0; j<10; j++) {
            if(!matrix[i][j]) {
                flag = false; 
                break;
            }
        }
        if(flag) result++;
    }

    return result;
}

int main() {
    char c;
    for(int i=0; i<20; i++) {
        for(int j=0; j<10; j++) {
            cin >> c;
            matrix[i][j] = c-'0';
        }
    }

    vector<minoStateList> minos {
        JMino, LMino, SMino, ZMino, TMino, IMino, OMino
    };

    int maxLine = 0;

    for(auto mino: minos) {
        for(auto minoState: mino) {
            vector<vector<bool> > isVisited(20, vector<bool>(10, false));
            queue<pair<int, int> > q;
            q.push({0, 0});

            while(!q.empty()) {
                int curY = q.front().first;
                int curX = q.front().second;
                q.pop();
                if(isVisited[curY][curX]) continue;
                isVisited[curY][curX] = true;

                bool flag = true;
                for(auto gap: minoState) {
                    int newY = curY+gap.first;
                    int newX = curX+gap.second;
                    if(!(newY<20 && newX<10 && !matrix[newY][newX])) {
                        flag = false;
                        break;
                    }
                }
                
                if(flag) {
                    bool gapFlag = false;
                    for(auto gap: minoState) {
                        int under = curY+gap.first+1;
                        if(under==20 || matrix[under][curX+gap.second]) {
                            gapFlag = true;
                            break;
                        }
                    }

                    if(gapFlag) {
                        for(auto gap: minoState) {
                            matrix[curY+gap.first][curX+gap.second] = true;
                        }
                        maxLine = max(maxLine, checkRemoveRowNum());
                        for(auto gap: minoState) {
                            matrix[curY+gap.first][curX+gap.second] = false;
                        }
                    }

                    for(int i=0; i<3; i++) {
                        int newY = curY+dy[i];
                        int newX = curX+dx[i];

                        if(newY<20 && newX>=0 && newX<10 && !isVisited[newY][newX]) {
                            q.push({newY, newX});
                        }
                    }
                }
            }
        }
    }

    cout << maxLine;
}

2. 챌린지반 과제

 

 

 일단 오늘 요구되는 건 모두 끝냈다. 여러 확장 가능성을 두고 짜느라, 아키텍처 디자인하고 보일러 플레이트 코드를 작성하느라 시간을 많이 쓴 것 같다. 그래도 어제까지 빡빡하게 해 놔서, 오늘 한 건 그냥 RecyclerView 구현하고 ViewModel과 Fragment를 연결해 준 것이 전부였다. 

 

 이런 구조에는 이제 좀 익숙해져서 빠르게 작성할 수 있게 되었는데, 확실히 관련 글도 많이 찾아보고 많이 만들어보니까 조금은 이해가 생긴 것 같다. 아키텍처랑 디자인 패턴을 처음 공부했던게 반년도 더 지났는데, 그때는 정말 낯설고 어렵게만 느껴졌던 걸 생각하면..

 

 

 

3. Git 연습

 오늘 소스트리를 이용해서 Git 관리하는 실시간 세션이 있었는데, 튜터님께서 올려주신 사이트에 들어가서 이것저것 공부해보았다. 기초적인 부분보다는 cherry-pick이나 rebase 등 평소에 잘 쓰지 않던 것들 위주로 보았는데, 도움이 많이 되었다.

 대부분의 형상관리 작업이 기초적인 명령들로 해결되지만, 몇몇 특수한 경우에는 써야할 일이 생기기 때문에 이번 기회에 이렇게 봐 두게 되어 좋았다. 일단 브랜치에 대한 디테일한 이해가 좀 더 생겼고, 커밋이 꼬였을 때 좀 더 다양한 솔루션을 생각해 볼 수 있을 것 같다.

 아무래도 아예 알지도 못하는 것과 한 번이라도 공부해서 키워드나 개념이라도 떠올릴 수 있는건, 어떤 솔루션을 찾는 과정에 있어서 정말 큰 차이를 보이니까. 나는 이런 점 때문에 무엇을 공부하더라도 넓게 이해해 본 다음, 깊게 들어가는 공부를 하게 되는 것 같다.