[프로그래머스] 131703 2차원 동전 뒤집기 (C/C++)

문제

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

풀이

문제를 처음 읽었을 때, 모든 경우를 완전탐색하는 방법밖에 떠오르지 않아 DFS를 통해 구현을 시도했다. 하지만 단순히 모든 칸을 뒤집거나 안 뒤집는 경우에 대한 완전탐색 풀이는 분명히 시간 초과가 발생할 것이라 확신했다.

이에 입력 범위를 확인해보았고, 최대 10×10 크기의 2차원 배열이 주어진다는 것을 알 수 있었다. 따라서, 모든 칸을 뒤집거나 안 뒤집는 경우의 수는

2^{10×10} = 2^{100} ≈ 10^{30}

정도로, 일반적인 제한 시간 내에는 처리할 수 없는 큰 수였다. 일반적으로 1초에 약 $10^{8}$ 번의 연산을 수행할 수 있고, 제한 시간은 2초임을 고려하면 시간 초과가 불가피했다.

문제를 다시 살펴보니, 각 칸의 뒤집기 여부는 해당 행과 열에만 영향을 받는다는 사실을 알 수 있었다. 또, 한 행과 열을 뒤집은 후에 다시 해당 행과 열을 뒤집는 것은 아무런 의미가 없다는 점도 알 수 있었다. 따라서, 행과 열 각각을 뒤집을지 말지를 결정하면 충분하며, 경우의 수는

2^{\text{행의 개수 + 열의 개수}}

로 줄어든다.

최대 10x10 크기의 2차원 배열임을 고려하면, 경우의 수는 최대

2^{10 + 10} = 2^{20} ≈ 10^{6}

로, 제한 시간 내에 충분히 처리할 수 있는 수가 된다.

소스 코드

C++17

#include <bits/stdc++.h>

std::pair<size_t, std::vector<std::vector<int>>> flip(const std::vector<std::vector<int>> &source, const std::vector<bool> &flag) {
    size_t count = 0;
    std::vector<std::vector<int>> flipped(source);

    for (size_t i = 0; i < flipped.size(); i++) {
        if (flag[i]) {
            count++;
            for (size_t j = 0; j < flipped[i].size(); j++) {
                flipped[i][j] ^= 1;
            }
        }
    }

    return { count, flipped };
}

std::pair<size_t, bool> convertable(const std::vector<std::vector<int>> &source, const std::vector<std::vector<int>> &target) {
    size_t count = 0;

    for (size_t j = 0; j < source[0].size(); j++) {
        bool flag = (source[0][j] == target[0][j]);

        for (size_t i = 1; i < source.size(); i++) {
            if (flag != (source[i][j] == target[i][j])) {
                return { 0, false };
            }
        }
        count += !flag;
    }

    return { count, true };
}

int solution(std::vector<std::vector<int>> beginning, std::vector<std::vector<int>> target) {
    const size_t N = beginning.size();
    const size_t M = beginning[0].size();

    std::function<int(std::vector<bool>, const size_t)>
    dfs = [&] (std::vector<bool> flag, const size_t last) {
        const auto &[ row, flipped ] = flip(beginning, flag);
        const auto &[ col, result ] = convertable(flipped, target);
        int ret = result ? row + col : INT_MAX;

        for (size_t i = last; i < N; i++) {
            flag[i] = true;
            ret = std::min(ret, dfs(flag, i + 1));
            flag[i] = false;
        }

        return ret;
    };

    int answer = dfs(std::vector<bool>(N, false), 0);

    return answer == INT_MAX ? -1 : answer;
}

[프로그래머스] 131703 2차원 동전 뒤집기 (C/C++)

문제

풀이

소스 코드

Share this post