[프로그래머스] 42894 블록 게임 (C/C++)
![[프로그래머스] 42894 블록 게임 (C/C++)](/assets/posts/01k85ac9909a6dcd6evmg1mgq5/index.png)
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42894
풀이
Ad-hoc 카테고리의 문제로, 주어진 조건에 맞게 구현하는 문제였다. Implementation이라고도 하며 흔히 말하는 빡구현 유형에 속한다.
물론 시간 복잡도를 고려해야한다. 간단히 계산해 봤을 때 성능상 문제가 없을 것 같다면, 이 문제는 ‘빡구현’ 카테고리임을 인식하고 접근하는 게 중요하다고 생각한다.
점점 기업 코딩테스트에서 Ad-hoc 문제가 자주 출제되는 것 같다. 좋은 흐름이라고는 생각되는데, Monito 등 여러 모니터링 시스템 속에서 다중 모니터, 클램쉘 등이 금지된 채 노트북 한 대로 코딩테스트를 치르는 환경에서는 이런 류의 문제가 알고리즘보다 훨씬 더 어렵게 느껴진다. 2026 카카오그룹 신입크루 공채가 카카오 창립 이래로 처음 이루어졌다. 최근에 코딩테스트를 응시했는데 다수의 문제가 Ad-hoc으로 구성되어있었고 너무 어려웠다.
이 문제도 2019 카카오 블라인드 채용 코딩테스트에 출제된 기출 문제인데 난이도가 상당히 높았다.
코드를 깔끔하게 작성하려는 강박이 조금 있는 편인데, Ad-hoc 문제에서는 이런 성향이 어려움으로 작용하는 것 같다.
일단 각 기능을 구현하고 단위 테스트를 진행하면서 문제를 해결하는데, 완성된 코드를 보면 라인의 수가 많아 가독성도 떨어지고 디버깅도 어렵다.
결국 어느 정도 구현한 후에 리팩토링을 진행하는데, 이 때 오류 없이 코드를 깔끔하게 정리하는 것이 쉽지 않다.
이번 풀이에서도 PATTERNS, REMOVABLE 이라는 상수를 도입해서 코드를 깔끔하게 하는데까지 꽤 시간이 걸렸다.
시행착오1
왼쪽 위부터 오른쪽 아래까지 차례대로 블록을 확인하면서 지울 수 없는 블록이 나타나면 col_is_blocked 배열을 갱신하는 방식으로 최적화를 진행했다.
하지만 위 그림처럼 L자 모양의 분홍색 블록이 먼저 감지되면, 해당 블록이 노란색 블록의 왼쪽 아래에 있음에도 불구하고 먼저 감지되어 위쪽에 있다고 잘못 판단되어 해당 열을 차단하는 문제가 발생했다.
이후에 매 반복마다 col_is_blocked 배열을 초기화하고, 매 반복마다 지울 블록들을 모아 한 번에 제거하는 방식으로 수정하여 문제를 해결했다.
시행착오2
시행착오1의 경우는 인지하고 있었지만 코드에 반영하지 못해 발생한 문제였다면, 시행착오2의 경우 전혀 예상하지 못한 반례였다.
위의 경우 노란색 블록이 분홍색 블록 아래에 있지만, 회색 칸이 채워지면 지워질 수 있는 형태였다.
이를 반영하기 위해 오래 고민하다가 CHECKS 라는 상수를 도입하여 해결했다.
소스 코드
#include <bits/stdc++.h>
typedef std::array<std::pair<int, int>, 4> Pattern;
constexpr Pattern PATTERNS[12] = {
{{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 } }},
{{ { 0, 0 }, { 0, 1 }, { 1, 0 }, { 2, 0 } }},
{{ { 0, 0 }, { 1, 0 }, { 1, 1 }, { 1, 2 } }},
{{ { 0, 1 }, { 1, 1 }, { 2, 0 }, { 2, 1 } }},
{{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 0 } }},
{{ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 2, 1 } }},
{{ { 0, 2 }, { 1, 0 }, { 1, 1 }, { 1, 2 } }},
{{ { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 1 } }},
{{ { 0, 1 }, { 1, 0 }, { 1, 1 }, { 1, 2 } }},
{{ { 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 0 } }},
{{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 1 } }},
{{ { 0, 1 }, { 1, 0 }, { 1, 1 }, { 2, 1 } }},
};
constexpr bool REMOVABLE[12] = {
false, false, true, true,
false, true, true, false,
true, false, false, false
};
const std::vector<std::pair<int, int>> CHECKS[12] = {
{}, {}, {{ 1, 1 }, { 1, 2 }}, {{ 2, 0 }},
{}, {{ 2, 1 }}, {{ 1, 0 }, { 1, 1 }}, {},
{{ 1, 0 }, { 1, 2 }}, {}, {}, {}
};
int solution(std::vector<std::vector<int>> board) {
int answer = 0;
const size_t N = board.size();
auto find_matched_pattern = [&] (const size_t row, const size_t col) -> int {
auto is_matched = [&] (const size_t number) -> bool {
const auto &pattern = PATTERNS[number];
size_t id = 0;
for (const auto &[ dr, dc ]: pattern) {
if (N <= row + dr || N <= col + dc) {
return false;
}
if (board[row + dr][col + dc] == 0) {
return false;
}
if (id == 0) {
id = board[row + dr][col + dc];
} else if (id != board[row + dr][col + dc]) {
return false;
}
}
return true;
};
for (size_t i = 0; i < 12; i++) {
if (is_matched(i)) {
return i;
}
}
return -1;
};
auto can_remove = [&] (const size_t row, const size_t col, const int pattern) -> bool {
if (pattern == -1 || !REMOVABLE[pattern]) {
return false;
}
for (const auto &[ tr, tc ]: CHECKS[pattern]) {
for (size_t r = 0; r < row + tr; r++) {
if (board[r][col + tc]) {
return false;
}
}
}
return true;
};
while (true) {
std::vector<std::tuple<int, int, int>> to_remove;
for (size_t row = 0; row < N; row++) {
for (size_t col = 0; col < N; col++) {
const int pattern = find_matched_pattern(row, col);
if (can_remove(row, col, pattern)) {
to_remove.push_back({ row, col, pattern });
}
}
}
if (to_remove.empty()) {
break;
}
answer += to_remove.size();
for (const auto &[ row, col, pattern ]: to_remove) {
for (const auto &[ dr, dc ]: PATTERNS[pattern]) {
board[row + dr][col + dc] = 0;
}
}
}
return answer;
}