[programmers] 고고학 최고의 발견

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

경우의 수 - 중복순열

 

---------------------------------------------------풀이----------------------------------------------------

 

clock의 첫 번째 row부터 정해나간다.

4번 회전시키면 원래 방향으로 돌아오므로, 0~3번 회전시키는 것만이 의미가 있다.

따라서, 첫 번째 row의 모든 clock을 0~3회 회전시킨다.

 

첫 번째 row의 회전 결과가 정해지면, 아래 row로 넘어가 위 row를 모두 0으로 만드는 과정을 거친다.

이미 회전시킨 위의 row를 바꿀 방법은 바로 아래의 row에서 clock을 회전시키는 방법 뿐이므로,

위를 0으로 만들도록 회전시킨다. 즉, 첫 번째 이후의 row들을 회전시키는 방법은 이미 정해져 있다.

이 방식으로 아래 row들을 계속해서 완성해 나갔을 때, 모두 0으로 만들어진다면 그 때의 cost의 min값을 찾으면 된다.

#include <string>
#include <vector>
#include <limits.h>

using namespace std;

// 위, 오, 아, 왼
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int clock_rots[10][10] = {0, };
vector<vector<int>> clocks;
int answer, N;

bool is_complete(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(clocks[i][j] != 0){
                return false;
            }
        }
    }
    return true;
}

// x,y 기준 인접한 모든 곳 90도 시계방향 회전
void rotate(int x, int y){
    clocks[x][y] = (clocks[x][y]+1)%4;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N){
            continue;
        }
        clocks[nx][ny] = (clocks[nx][ny]+1)%4;
    }
}

// x,y 기준 인접한 모든 곳 90도 반시계방향 회전
void restore(int x, int y){
    clocks[x][y]--;
    if(clocks[x][y] < 0) clocks[x][y] = 3;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N){
            continue;
        }
        clocks[nx][ny]--;
        if(clocks[nx][ny] < 0) clocks[nx][ny] = 3;
    }
}

// 윗줄에 맞춰서 아랫줄 돌리기
void decide_all(int cost, int row){
    if(is_complete()){
        if(cost < answer){
            answer = cost;
        }
        return;
    }
    if(row >= N || cost >= answer){
        return;
    }
    vector<int> rotates;
    for(int i = 0; i < N; i++){
        int cur_rots = 0;
        while(clocks[row-1][i] != 0){
            rotate(row, i);
            cost++;
            cur_rots++;
        }
        rotates.push_back(cur_rots);
    }
    decide_all(cost, row+1);
    for(int i = 0; i < N; i++){
        while(rotates[i]--){
            restore(row, i);
        }
    }
}

void decide_first_row(int col, int cost){
    if(col >= N){
        decide_all(cost, 1);
        return;
    }
    int cur_cost = 0;
    // 돌리지 않고 다음으로 넘어감
    decide_first_row(col+1, cost+cur_cost);
    // 1~3번 돌리고 다음으로 넘어감
    for(int i = 0; i < 3; i++){
        rotate(0, col);
        cur_cost++;
        decide_first_row(col+1, cost + cur_cost);
    }
    while(cur_cost--){
        restore(0, col);
    }
}

// 시계가 행렬을 이룸. 하나의 시계에 시곗바늘 하나씩.
// 한 번에 90도씩 시계방향으로 돌릴 수 있음.
// 상하좌우 인접한 시계도 함께 돌아감.
// 모든 시계가 12시를 가리키면 종료. 최소의 조작 횟수=?
int solution(vector<vector<int>> clockHands) {
    answer = INT_MAX;
    clocks = clockHands; N = clockHands.size();
    // 맨 윗줄을 정해줌. => 각각 0~3번씩 돌림 => max : 4^8
    decide_first_row(0, 0);
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

dfs로 모든 케이스를 찾으려 했을 때, 계속해서 시간초과로 고생했다.

아무리 가지치기를 해도 불가능했다.

row, col을 넘겨주며 그 이후부터 돌리는 방식을 했지만, 최대 길이가 8일다보니, 경우의 수가 너무 증가했다.

 

첫 번째 row를 정해주면, 다음 row의 clock들은 위의 row를 모두 0으로 만드는 방향으로만 회전할 수 있다는 것을 깨닫고, 이 방식으로 구현해 성공했다.

첫 row를 정한는 것은 중복순열이므로 최대 4^8이다.