고고학 최고의 발견(미해결)

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

풀이(40점)

질문하기의 반례들은 통과하는데 채점하면 10문제 중 6문제 틀린다. 반례 찾기.

#include <string>
#include <vector>

using namespace std;
int check[9], e, N, M;
int dr[5] = {0, -1, 0, 1, 0};
int dc[5] = {0, 0, 1, 0, -1};
int mini = 2147000000;

// 1. 0행을 돌리는 경우를 구한다.예: (0, 0, 0, 1) == 0행 3열 블록 1번 돌림.
// 2. 0행부터 0이 아닌 경우 i + 1번째를 돌린다.
void DFS(int L, vector<vector<int>> clockHands)
{
    if(L == e)
    {
        int sum = 0;
        // check배열 따라 0행 돌린다.
        for(int i = 0; i < e; ++i)
        {
            if(check[i] == 0) continue;
            // check[i]번 만큼 돌려야 함.
            for(int k = 0; k < 5; ++k)
            {
                int check_r = dr[k];
                int check_c = i + dc[k];
                
                if(check_r < 0 || check_c < 0 || check_r >= N || check_c >= M) continue;
                clockHands[check_r][check_c] = (clockHands[check_r][check_c] + check[i]) % 4;
            }
            sum += check[i];
        }
        // 0행부터 돌리며 0이 아닌 경우 i + 1을 돌림.
        for(int i = 0; i < N - 1; ++i)
        {
            for(int j = 0; j < M; ++j)
            {
                if(clockHands[i][j] == 0) continue;
                while(clockHands[i][j] != 0)
                {
                    for(int k = 0; k < 5; ++k)
                    {
                        int check_r = (i + 1) + dr[k];
                        int check_c = j + dc[k];
                        
                        if(check_r < 0 || check_c < 0 || check_r >= N || check_c >= M) continue;
                        clockHands[check_r][check_c] = (clockHands[check_r][check_c] + 1) % 4;
                    }
                    ++sum;
                }
            }
        }
        if(mini > sum) mini = sum;
    }
    else
    {
        for(int i = 0; i < 4; ++i)
        {
            check[L] = i;
            DFS(L + 1, clockHands);
        }
    }
}

int solution(vector<vector<int>> clockHands) {
    int answer = 0;
    N = clockHands.size();
    M = clockHands[0].size();
    e = N;
    
    DFS(0, clockHands);
    
    return answer = mini;
}