[Algorithm] Programmers :: 고고학 최고의 발견

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

프로그래머스

int answer = 0x3f3f3f3f;
int width, height = 0;
int dir[5][2] = { {0,0}, {-1,0}, {1,0}, {0,-1}, {0,1} };
 
void Rotate(int y, int x, int rotateCount, vector<vector<int>>& board)
{
    for (int i = 0; i < 5; ++i)
    {
        int nextY = y + dir[i][0];
        int nextX = x + dir[i][1];
 
        if (nextY < 0 || nextY == height) continue;
        if (nextX < 0 || nextX == width) continue;
 
        board[nextY][nextX] = (board[nextY][nextX] + rotateCount) % 4;
    }
}
 
void DFS(int col, int answerCount, vector<vector<int>> board)
{
    if (col == width)
    {
        for (int i = 1; i < height; ++i)
        {
            for (int j = 0; j < width; ++j)
            {
                int rotateCount = (4 - board[i - 1][j]) % 4;
                Rotate(i, j, rotateCount, board);
                answerCount += rotateCount;
            }
        }
 
        for (int i = 0; i < width; ++i)
        {
            if (board[height - 1][i] != 0)
            {
                return;
            }
        }
 
        answer = min(answer, answerCount);
 
        return;
    }
 
    for (int i = 0; i < 4; ++i) // 회전 안하기 + 회전3번
    {
        if (i >= 1) Rotate(0, col, 1, board);
 
        DFS(col + 1, answerCount + i, board);
    }
}
 
int solution(vector<vector<int>> clockHands)
{
    width = clockHands[0].size();
    height = clockHands.size();
 
    DFS(0, 0, clockHands);
 
    return answer;
}

그리디 + 탐색문제이다.

 

완전탐색으로 하려면 시간복잡도가 4 ^ 64승이 나오기 때문에 불가능하다.

그렇기 때문에 탐색횟수를 최소한으로 줄여야 한다.

 

근데 더 중요한 건, 어쨌든 결국 전부 0으로 만들어야한다는 것이다.

전부 0으로 만들 수 있는 확실한방법은 n+1번째 행의 회전을 통해 n번째 행을 전부 0으로 만드는 것이다.

그렇게 마지막행까지 진행한다음, 마지막행의 각 열값이 전부 0이면 일단 문제의 조건엔 충족하게 된다.

 

다만 최소한의 회전을 구해야 한다.  그러기위해 첫번째 행의 열값들을 DFS를 통해 하나씩 회전시켜본다.

물론 회전을 안한다는 경우의수도 있다는 걸 잊으면 안된다.

그러면 회전안하기 + 회전3번 => 총 4번의 경우의 수가 각 열마다 진행되고, 최대 크기는 8이니까 8 ^ 4의 경우의 수가 발생한다. 

그리고 해당 경우의 수마다 위의 그리디한 로직을 수행하는데, 해당 로직도 0으로 만들기위한 회전을 할 때 행 하나를 빼고 전부 탐색하며 그다음 마지막 행의 열값들이 전부 0인걸 체크하기위해 한 행을 쭉 훑으니까 결국 board전체를 탐색하게된다. 그러면 8*8이니까 결국 8^4 * 8 * 8 => 8 ^ 6 정도의 시간복잡도로 결론이 난다. ( 위 코드 기준 )

 

정확한건 아니고.. Rotate함수는 뺀거라서 대략적으로 8 ^ 6 이라는 것이다.