카카오 신입 공채 1차 코딩 테스트 풀이 - 6번문제


작성일 : 2018-06-03 18:51:29
조회수 : 913



본문

6번 문제입니다. 6번 문제는 전형적인 시뮬레이션 문제입니다. 보드의 크기도 30*30을 넘지 않고, 한번에 없어지는 블록의 개수도 많기 때문에 정말 말 그대로 게임을 규칙에 맞게 진행하며 처리를 하면 됩니다.


문제 자체는 굉장히 쉬우나 난이도가 상으로 채택된 이유는 아마 블로그의 코멘트처럼 "짜야 될 코드가 많아서" 인 것이 큰 것 같습니다. 또 블럭이 떨어질 때 구현을 처음할 때는 어떻게 해야되는지 감이 안 오는 경우가 있을수도 있겠네요. 임의의 $(i,j)$ 번째 있는 블럭이 밑으로 떨어지는 경우는 아래가 바닥일 때밖에 없습니다. 즉, 1칸씩 계속 내려보내면서 바닥이 나오면 멈추어주면 됩니다. 모든 것을 그대로 구현하면 됩니다.


int solve(int m,int n,vector<string> board)

{

    

    bool isFinished;

    int ans = 0;


    while (1) {

        isFinished = true;

        bool f[31][31] = { 0 };

        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {

                char a = board[i - 1][j - 1], b = board[i - 1][j], c = board[i][j - 1], d = board[i][j];

                if (a == b&&b == c&&c == d)

                {

                    if (a == '-') continue;

                    isFinished = false;

                    f[i - 1][j - 1] = f[i - 1][j] = f[i][j - 1] = f[i][j] = true;

                }

            }

        }


        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (f[i][j]) board[i][j] = '-';

            }

        }

        for (int i = 0; i < n; i++) {

            for (int j = m-1; j >=0 ; j--) {

                int tj = j;

                while (tj + 1 < m && board[tj+1][i] == '-') {

                    swap(board[tj][i], board[tj + 1][i]);

                    tj++;

                }

            }

        }

        if (isFinished) break;

    }

    for (int i = 0; i < m; i++) {

        for (int j = 0; j < n; j++) {

            if (board[i][j] == '-') ans++;

        }

    }

    return ans;

}

카카오 신입 공채 1차 코딩 테스트 풀이 - 6번문제 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.