[프로그래머스] 블록 게임

2019 카카오 채용 코딩 테스트 문제입니다.

코딩테스트 연습 - 블록 게임

문제 확인

 

구현 문제입니다.

 

풀이

 

블록을 3x3 크기기에서 경우의 수를 두어 풉니다.

1 2 3

4 5 6

7 8 9

위와 같은 배치에서 문제에서 주어진 블록의 형태는 ㄴ, ㅗ 를 뒤집거나 회전하여 만들 수 있는 형태만 주어집니다. 따라서 위에서 블록을 떨어뜨려 속이 채워진 직사각형을 만들 수 있는 경우의 수는 다음과 같습니다.

다시 말해 위에서 블록을 떨어뜨렸을때 채울 수 없는 공간이 없는 형태의 도형이 문제의 답이 됩니다. 이러한 형태의 도형은 항상 1, 2, 3번 위치에서 먼저 도형의 시작점을 만날 수 있으며 조건식을 통해 도형이 맞는지 확인하고 반영하면 됩니다.

 

주의해야 할 점은 위와같은 도형의 형태를 가지더라도 다음과 같은 경우 채울 수 없습니다.

이를 위해 채우기 불가능한 경우 현재 도형이 포함된 3번째 줄(2,5,8), 4(3,6,9)번째 세로 줄을 불가능한 줄로 만들어버려 다음 탐색 시 이를 반영합니다.

 

위에서부터 탐색하는 저의 방법을 사용하는 경우 한 가지 더 고려해야 할 점이 있습니다.

위와 같은경우 초록색 도형을 먼저 만나기 때문에 채울 수 없다고 판단하고 넘어가는 경우 답을 틀리게 됩니다. 이를 위해 현재 도형이 채울 수 있는 도형이라면 채우고 난 후 몇 개의 칸을 돌아가서 이전 도형이 채워질 수 있는지 다시 확인을 해야 합니다.

#define go_back(x,n) x>=n?x-n:0

여기서 n의 값은 현재 도형의 형태에 따라 선택해야 합니다. 위와 같은 경우 3칸들 뒤로 돌아가서 확인을 하면 됩니다. 그 이유는 채울 수 있는 도형의 형태 중에는 (1,4,5,6) 길게 늘어진 ㄴ 형태의 도형도 있기 때문에 3칸을 돌아가서 검사하여야 합니다.

 

코드

#include <string>
#include <vector>
using namespace std;
#define go_back(x,n) x>=n?x-n:0
 
/*
1 2 3
4 5 6
7 8 9
*/
bool check(vector<vector<int>> &board, int max_i, int j) {
    for (int i = max_i; i >= 1; i--) {
        if (board[i][j])return false;
    }
    return true;
}
 
int solution(vector<vector<int>> board) {
    int answer = 0, n = board.size();
    bool impossible[52] = { 0 }, visited[201] = { 0 };
    for (auto &i : board) { i.insert(i.begin(), 0); i.push_back(0); }
 
    board.emplace(board.begin(), n + 2, 0);
    board.emplace_back(n + 2, 0);
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (board[i][j]) {
                int cur = board[i][j];
                if (visited[cur]) continue;
                if (board[i][j + 1] == cur) {//1247, 1258
                    impossible[j + 1] = impossible[j] = 1;
                    if (board[i][j + 2] == cur)//1234, 1235, 1236
                        impossible[j + 2] = 1;
                    visited[cur] = 1;
                }
                if (board[i + 1][j] == cur) {
                    if (board[i + 1][j - 1] == cur && board[i + 1][j + 1] == cur) { // 2456
                        if (impossible[j - 1] || impossible[j + 1] || !check(board, i, j + 1)) { 
                            impossible[j - 1] = impossible[j] = impossible[j + 1] = 1;
                        }
                        else {
                            board[i][j] = board[i + 1][j + 1] = board[i + 1][j] = board[i + 1][j - 1] = 0;
                            j = go_back(j, 3);
                            answer++;
                        }
                        visited[cur] = 1;
                    }
                    else if (board[i + 1][j - 1] == cur) {
                        if (board[i + 1][j - 2] != cur) {//3659
                            impossible[j - 1] = impossible[j] = 1;
                        }//3456
                        else if (impossible[j - 2] || impossible[j - 1] || !check(board, i, j - 2) || !check(board, i, j - 1)) {
                            impossible[j] = impossible[j - 1] = impossible[j - 2] = 1;
                        }
                        else {
                            board[i][j] = board[i + 1][j] = board[i + 1][j - 1] = board[i + 1][j - 2] = 0;
                            j = go_back(j, 4);
                            answer++;
                        }
                        visited[cur] = 1;
                    }
                    else if (board[i + 1][j + 1] == cur) {
                        if (board[i + 1][j + 2] != cur) {//1457
                            impossible[j + 1] = impossible[j] = 1;
                        }//1456
                        else if (impossible[j + 1] || impossible[j + 2] || !check(board, i, j + 1) || !check(board, i, j + 2)) {
                            impossible[j + 2] = impossible[j + 1] = impossible[j] = 1;
                        }
                        else {
                            board[i][j] = board[i + 1][j + 2] = board[i + 1][j + 1] = board[i + 1][j] = 0;
                            j = go_back(j, 2);
                            answer++;
                        }
                        visited[cur] = 1;
                    }
                    else if (board[i + 2][j] == cur) {
                        if (board[i + 2][j - 1] == cur) {//2587
                            if (!impossible[j - 1] && check(board, i + 1, j - 1)) {
                                board[i + 2][j] = board[i + 2][j - 1] = board[i + 1][j] = board[i][j] = 0;
                                answer++;
                            }
                        }
                        else if (board[i + 2][j + 1] == cur) {//2587
                            if (!impossible[j + 1] && check(board, i + 1, j + 1)) {
                                board[i + 2][j + 1] = board[i + 2][j] = board[i + 1][j] = board[i][j] = 0;
                                answer++;
                            }
                        }
                    }
                }
            }
        }
    }
    return answer;
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.95MB)
테스트 2 〉	통과 (0.01ms, 3.97MB)
테스트 3 〉	통과 (0.03ms, 3.95MB)
테스트 4 〉	통과 (0.01ms, 3.97MB)
테스트 5 〉	통과 (0.01ms, 3.9MB)
테스트 6 〉	통과 (0.01ms, 3.96MB)
테스트 7 〉	통과 (0.01ms, 3.9MB)
테스트 8 〉	통과 (0.01ms, 3.96MB)
테스트 9 〉	통과 (0.02ms, 3.94MB)
테스트 10 〉	통과 (0.02ms, 3.95MB)
테스트 11 〉	통과 (0.02ms, 3.96MB)
테스트 12 〉	통과 (0.05ms, 3.93MB)
테스트 13 〉	통과 (0.05ms, 3.7MB)
테스트 14 〉	통과 (0.04ms, 3.94MB)
테스트 15 〉	통과 (0.05ms, 3.96MB)
테스트 16 〉	통과 (0.04ms, 3.95MB)
테스트 17 〉	통과 (0.04ms, 3.93MB)
테스트 18 〉	통과 (0.05ms, 3.96MB)
테스트 19 〉	통과 (0.05ms, 3.95MB)
테스트 20 〉	통과 (0.01ms, 3.96MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0