[C++][프로그래머스] 고고학 최고의 발견 🔥

프로그래머스

 

📄 문제

고고학자인 혜선은 오래전부터 성궤의 행방을 추적해왔습니다. 그동안 그의 연구는 주류 학자들로부터 인정받지 못했었지만, 혜선이는 포기하지 않고 조사를 계속했고 마침내 성궤의 행방을 알아내었습니다.

그러나 오래전 누군가로부터 봉인된 성궤는 특별한 잠금장치에 의해 보호되고 있었습니다. 잠금장치는 일종의 퍼즐과 연결되어 퍼즐을 해결하면 열리는 것으로 보입니다.

퍼즐은 시계들이 행렬을 이루는 구조물인데 하나의 시계에 시곗바늘은 하나씩만 있습니다. 각 시곗바늘은 시계방향으로만 돌릴 수 있고 한 번의 조작으로 90도씩 돌릴 수 있습니다. 시계들은 기계장치에 의해 연결되어 있어 어떤 시계의 시곗바늘을 돌리면 그 시계의 상하좌우로 인접한 시계들의 시곗바늘도 함께 돌아갑니다. 행렬의 모서리에 위치한 시계의 시곗바늘을 돌리는 경우에는 인접한 세 시계의 시곗바늘들이 함께 돌아가며, 꼭짓점에 위치한 시계의 시곗바늘을 돌리는 경우에는 인접한 두 시계의 시곗바늘들이 함께 돌아갑니다.

각 시계는 12시, 3시, 6시, 9시 방향 중의 한 방향을 가리키고 있습니다. 각 시계의 시곗바늘을 적절히 조작하여 모든 시곗바늘이 12시 방향을 가리키면 퍼즐이 해결되어 성궤를 봉인하고 있는 잠금장치가 열릴 것입니다.

노후화된 퍼즐 기계장치가 걱정되었던 혜선은 가능한 최소한의 조작으로 퍼즐을 해결하려고 합니다. 시곗바늘들의 행렬 clockHands가 매개변수로 주어질 때, 퍼즐을 해결하기 위한 최소한의 조작 횟수를 return 하도록 solution 함수를 완성해주세요.

 

📝 풀이

• DFS를 (0, 0)위치에서 부터 시작하여 clockHands의 모든 영역에 대하여 0, 1, 2, 3번씩 회전했을 때를 고려하여 clockHands의 현 상태가 모두 정렬이 되었다면, 해당 형상까지 총 몆번을 회전하였는지 검사할 수 있습니다.
  • 하지만 이 방법대로 문제를 해결한다면 모든 경우의 수는 매우 커지므로, 시간 초과가 나 조금 더 효율적인 방법을 고려해야합니다.
• 아래의 규칙을 따라 더 효율적인 방식으로 문제를 해결할 수 있습니다.
  • (0, 0)부터 회전을 시도하여 경우의 수를 늘려나갑니다.
  • 현재 행에서 모든 열까지 회전을 한 후 , 행을 늘려나갑니다. (0, 0) -> (0, 1) -> ... -> (0, 3) -> (1, 0)
  • 행이 1 이상인경우, 현재 위치(row, col)에서 0~3번의 회전을 하였을 때  row - 1의 값이 1이어서는 안됩니다. 그 이유는 위 규칙에 의해 검사는 (0, 0)위치로부터 차례대로 진행되며, 위 값이 0이 아니라면, 더 이상 해당 값을 되돌릴 수 없기 때문입니다.
    • 행이 1 이상인 상태에서, row - 1의 값이 0이라면, 해당 경우의 수는 모든 시계를 정렬할 수 있는 가능성이 있으므로 DFS를 누적하여 호출할 수 있습니다.
  • 만약, check 함수가 true로 나온다면, 누적된 cnt의 값을 리턴합니다. row의 값이 size와 같아진다면, 영역을 초과할 때 까지 check에 성공하지 못한것으로, INT_MAX를 리턴하여 해당 값은 사용하지 않게합니다.

#include <string>
#include <vector>
#include <iostream>
#include <climits>

using namespace std;

int dy[5] { 0, 0, 0, 1, -1 };
int dx[5] { 0, -1, 1, 0, 0 };
int result = INT_MAX;

// 선택한 (y, x)의 위치를 isClockwise 방향으로 회전
void rotate(vector<vector<int>>& clockHands, int y, int x, int count, bool isClockwise = true)
{
    // 선택된 위치를 기준으로 5번의 반복(현재 위치, 좌, 우, 상, 하)
    for(int i = 0; i < 5; ++i)
    {
        int yy = y + dy[i];
        int xx = x + dx[i];
        
        // 영역 자체를 벗어났다면, 수행하지 않음
        if(yy == -1 || xx == -1 || yy == clockHands.size() || xx == clockHands.size())
            continue;
        
        // isClockwise(시계 방향)이라면, +count(시계방향) 아니라면 -count(시계반대방향)
        clockHands[yy][xx] = clockHands[yy][xx] + (isClockwise ? +count : -count);
        
        // -값이 되면 적절하게 수정
        if(clockHands[yy][xx] < 0)
            clockHands[yy][xx] += 4;

        // 3보다 커질 수 없기에 적절히 수정
        clockHands[yy][xx] %= 4;
    }
}

// 현재 형상이 모두 12시로 맞춰져 있는가?
bool check(vector<vector<int>>& clockHands)
{
    for(int i = 0; i < clockHands.size(); ++i)
        for(int j = 0; j < clockHands.size(); ++j)
            if(clockHands[i][j])
                return false;
    
    return true;
}

int DFS(vector<vector<int>>& clockHands, int row, int col, int cnt)
{
    // 모든 시계를 확인하고 최소 이동 횟수 업데이트
    if (check(clockHands))
        return cnt;
    
    // 마지막에 도달하였을 때, check가 안되었다면, 이 방법으로는 시계를 정렬할 수 없음
    if (row == clockHands.size())
        return INT_MAX;  
    
    // 만약 누적된 cnt가 result 이상이라면, 더 이상 검사할 필요가 없기에 리턴
    if (cnt >= result)
        return INT_MAX;
    
    // 해당 위치를 0~3번 돌려 경우의수를 확장
    for (int i = 0; i < 4; ++i) 
    {
        // i만큼 시계 방향으로 회전
        rotate(clockHands, row, col, i, true);
        
        // 현재 row가 1 이상이면서, 현재 위치 바로 위 값이 0이 아니라면? -> 누적된 이 방법으로는 시계를 맞출 수 없음
        if (row && clockHands[row - 1][col]) 
        {
            // 회전 전으로 복구(반시계 방향 회전)
            rotate(clockHands, row, col, i, false);
            continue;
        }
        
        // 다음 위치 계산
        int nextRow = (col + 1 == clockHands.size()) ? row + 1 : row; // col이 끝에 도달하였다면, row를 증가, 아니라면 유지
        int nextCol = (col + 1) % clockHands.size(); // 다음 col은 1씩 증가
        
        // cnt는 i만큼 더하기 (i만큼 회전한 것이기 때문)
        result = min(result, DFS(clockHands, nextRow, nextCol, cnt + i));
        
        // 재귀가 끝나면 원래 상태로 되돌리기
        rotate(clockHands, row, col, i, false);
    }
    
    return result;
}

int solution(vector<vector<int>> clockHands) {
    return DFS(clockHands, 0, 0, 0);
}