Problem SolvingJul 23, 2026

[프로그래머스] 131702 고고학 최고의 발견 (C/C++)

#Problem Solving#Coding Test#Algorithm#Programmers#131702#C/C++#Implementation#Brute Force#Simulation
[프로그래머스] 131702 고고학 최고의 발견 (C/C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131702



풀이

입력의 제한 조건이 최대 8 x 8 크기의 matrix인 것을 확인했다. 입력 크기 자체는 충분히 작다고 판단했고, 결국 어떤 방식으로 탐색 범위를 줄이느냐가 핵심인 문제라고 생각했다.

우선 Greedy한 접근과 동적 계획법은 유효하지 않을 것이라 판단했다. 현재 선택한 최적값이 이후의 최적값까지 보장한다고 보기 어려웠기 때문이다. 2시간 정도 고민했는데, 여전히 완전 탐색 말고는 방법이 없을 것 같다는 느낌이 있었다. 하지만 모든 칸을 각각 몇 번 조작할지 완전 탐색하면 시간 복잡도가 O(4N2)O(4^{N^2})이 되므로 불가능한 풀이였다. 조금 더 고민하다가, 한 칸을 조작한 뒤 다른 칸을 조작하고 다시 이전 칸으로 돌아올 필요는 없다는 것을 깨달았다.

예를 들어 (0, 0)을 움직인다고 하자. 한 칸을 조작하면 상하좌우의 인접한 칸에도 영향을 끼치므로, 이후 (1, 0)을 움직이면 (0, 0)의 값도 다시 바뀐다. 이때 (0, 0)을 다시 움직여서 그 변화를 해결한다고 해도, 처음 (0, 0)을 움직일 때 그만큼의 횟수를 미리 더해서 움직이면 결국 같은 결과를 만들 수 있다. 따라서 한 번 조작을 확정한 칸은 다시 조작할 필요가 없고, 한 방향으로 순회하면서 각 칸의 조작 횟수를 확정할 수 있음을 알았다. 이후 남은 것은 어떤 값을 완전 탐색할 것인가였다.

행 방향으로 탐색한다면, 위 로직대로 (0, 0)을 조작한 뒤 (1, 0)까지 조작하면, (0, 0)은 더 이상 다른 행을 조작해서 맞출 수 없다. 즉, 이전 행의 값을 맞추기 위해 현재 행에서 몇 번 조작해야 하는지가 강제로 결정된다. 따라서 첫 번째 행의 조작 횟수를 정하면, 이후 행들의 조작 횟수는 이전 행의 상태에 따라 연쇄적으로 단 하나의 경우로 고정된다. 결국 첫 번째 행에서 가능한 모든 조작 경우의 수인 4N4^N만 완전 탐색하고, 각각의 경우에 대해 아래 행의 조작 횟수를 순서대로 결정하는 방식으로 문제를 해결했다.

각 경우마다 전체 matrix를 한 번 순회하므로 최종 시간 복잡도는 O(4N×N2)O(4^N \times N^2)이다.


항상 이런 타입의 문제를 마주할 때마다, 알고리즘이 떠오르지 않으면 그냥 풀지 말라는 건가 싶었다.

그래프 탐색이나 최단 경로처럼 이름이 붙어 있는 알고리즘 문제는 적어도 무엇을 공부해야 하는지는 알 수 있다. 반면 Implementation이나 Simulation 문제는 문제마다 별도의 로직을 새로 발명해야 하는 것처럼 느껴졌다. 결국 핵심 통찰을 떠올리지 못하면 틀릴 수밖에 없고, 그 통찰을 찾는 과정은 운에 가깝다고 생각했다.

이번 문제도 처음에는 비슷했다. 모든 칸을 완전 탐색하는 것은 불가능하다는 것까지는 알았지만, 어디서 탐색 범위를 줄여야 할지 쉽게 찾지 못했다.

그런데 풀이를 정리하면서, 조작 순서가 결과에 영향을 주지 않는지 확인하거나 일부 상태를 결정했을 때 나머지 상태가 강제로 정해지는지를 살펴보는 것이 이런 문제에서 자주 사용되는 패턴이라는 것을 알게 됐다. 나는 이런 관찰 자체가 문제마다 새롭게 떠올려야 하는 전용 로직이라고 생각했는데, 어느 정도는 반복해서 등장하는 접근 방식이었던 것 같다.

결국 이런 유형을 잘 풀기 위해서는 문제를 많이 푸는 것뿐만 아니라, 풀이에서 사용한 관찰을 문제 하나의 아이디어로만 남기지 않고 일반적인 패턴으로 정리해 둘 필요가 있어 보인다. 지금까지는 정답을 이해하고 넘어가는 데 그쳤다면, 앞으로는 어떤 관찰이 다른 문제에서도 반복될 수 있는지까지 확인해야겠다.

물론 실제 문제를 마주했을 때 그 패턴을 알아보는 것은 여전히 어렵다,,



소스 코드

C++17
#include <bits/stdc++.h>

constexpr size_t INF = 1'000'000;
constexpr std::array<std::pair<int, int>, 5> DIRECTIONS = {{
    {  0,  0 },
    { -1,  0 },
    {  0,  1 },
    {  1,  0 },
    {  0, -1 }
}};

size_t evaluate(std::vector<std::vector<int>> clock_hands, std::vector<size_t> to_rotate) {
    const size_t N = clock_hands.size();
    const auto out_of_range = [&] (const int r, const int c) {
        return r < 0 || N <= r || c < 0 || N <= c;
    };
    size_t ret = 0;

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            for (const auto [ dr, dc ]: DIRECTIONS) {
                const int nr = dr + r;
                const int nc = dc + c;

                if (out_of_range(nr, nc) == false) {
                    clock_hands[nr][nc] = (clock_hands[nr][nc] + to_rotate[c]) % 4;
                }
            }
        }
        for (size_t c = 0; c < N; c++) {
            ret += to_rotate[c];
            to_rotate[c] = (4 - clock_hands[r][c]) % 4;
        }
    }

    return std::any_of(
        to_rotate.cbegin(),
        to_rotate.cend(),
        [] (const size_t count) { return count; }
    ) ? INF : ret;
}

int solution(std::vector<std::vector<int>> clock_hands) {
    const size_t N = clock_hands.size();
    std::vector<size_t> to_rotate(N);
    size_t answer = INF;

    const auto update = [&] (std::vector<size_t> &vector) -> bool {
        for (size_t c = 0; c < N; c++) {
            if (++vector[c] < 4) {
                return true;
            }
            vector[c] = 0;
        }
        return false;
    };

    do {
        answer = std::min(answer, evaluate(clock_hands, to_rotate));
    } while (update(to_rotate));

    return answer;
}

Share this post

N