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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음 이 문제를 봤을 때 어떻게 풀어야 할지 오래 고민했다.

열쇠의 모양이 십자 모양이기 때문에 맨 위 부분만 파악할 수 있으면 쉽게 풀 수 있지만, 열쇠의 정 중앙이 성궤의 테두리에 놓일 수 있기 때문이었다.

 

그렇게 고민하던 중 다른 사람의 힌트를 봤고, 모든 경우를 전부 탐색할 필요는 없이 첫 줄만 결정하면 된다는 것이었다.

맨 위 부분만 판단하면 되는 이유는 위 그림을 보면 알 수 있다.

양 옆에 다른 열쇠 조각에 영향을 끼치는 부분은 가운데 줄에 위치해야만 가능하다.

 

그렇기 때문에 남은 조각을 탐색했을 때, 맨 위 조각이 12시가 아닌 상태라면 무조건 그 아래에 있는 부분을 돌려 12시를 맞춰야 하기 때문이다.

 

좀 더 자세하게 예를 들면

맨 윗줄은 횟수가 정해졌다고 가정하자.

그렇다면 이제 맨 윗줄의 방향을 바꿀 수 있는 부분은 열쇠의 중앙이 오는 부분은 2번째 줄밖에 없다.

여기서 3의 좌표가 (1,2)이라고 하면, (1, 2) 부분의 방향을 바꿀 수 있는 부분은 바로 아래 부분인 (2, 2)밖에 없다.

 

그렇기 때문에 9시를 가리키는 (1,3)을 0으로 만들기 위해서는 (2, 2)를 1번 돌려야 한다.

 

이제 이 방법을 사용하기 위해서 맨 윗줄은 모든 경우를 탐색해 주어야 한다. 

위 그림에서 X친 부분을 알고 있다면, 단순히 탐색하는 것 만으로도 첫째 줄에 열쇠를 몇번씩 돌릴지 알 수 있지만 X친 부분은 경계부분이기 때문에 정보가 주어지지 않는다.

그래서 맨 윗줄은 0~3의 모든 경우를 각 칸에 넣어서 탐색을 해야 잠금장치를 최소 횟수로 여는 경우를 알 수 있게 된다.

즉 (4^잠금장치의 길이)의 경우만큼 계산을 해주어야 한다.

 

 

 

​

[아이디어 정리]

1. 십자 모양으로 방향이 돌아가므로 위에서 부터 탐색을 시작하면, 십자 부분의 맨 위 부분의 방향을 돌리기 위해 바로 아래에 퍼즐을 돌려야한다.
2. 맨 윗 줄은 경계로 그 위에 상단이 보이지 않으므로, 모든 경우를 탐색하며 가능한지 판단해야한다.
3. 모든 경우를 탐색해 그 중 성궤가 열리면서, 가장 회전 횟수가 적은 값을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int dy[5]={1,-1,0,0,0};
int dx[5]={0,0,0,1,-1};
int minAns = 10000000;

void Calc(int maxSize, int nowIndex, vector<vector<int>> &topValue, vector<vector<int>> &clockHands)
{
    if (nowIndex<maxSize)
    {
        for (int i=0; i<=3; i++)
        {
            topValue[0][nowIndex]=i;
            Calc(maxSize,nowIndex+1,topValue,clockHands);
        }    
    }
    else
    {
        vector<vector<int>> realClockHands=clockHands;        
        int y=0,x=0,ny,nx;
        for (int i=0; i<maxSize; i++)
        {
            x=i;
            for (int j=0; j<5; j++)
            {
                ny=y+dy[j];
                nx=x+dx[j];
                if (ny>=0 &&ny<maxSize&&nx>=0&&nx<maxSize)
                {
                    realClockHands[ny][nx]+=topValue[0][i];
                    realClockHands[ny][nx]%=4;
                }
            }
        }
        
        for (int i=0; i<maxSize-1; i++)
        {
            y=i+1;
            for (int j=0; j<maxSize; j++)
            {
                x=j;
                if (realClockHands[i][j]!=0)
                {
                    int vvv=4-realClockHands[i][j];
                    topValue[y][j]=vvv;
                    for (int k=0; k<5; k++)
                    {
                        ny=y+dy[k];
                        nx=x+dx[k];
                        if (ny>=0 &&ny<maxSize&&nx>=0&&nx<maxSize)
                        {
                            realClockHands[ny][nx]+=vvv;
                            realClockHands[ny][nx]%=4;
                        }
                    } 
                }
                else
                {
                    topValue[y][j]=0;
                }
            }
        }
        int ttt=0;
        for (int i=0; i<maxSize; i++)
        {
            for (int j=0; j<maxSize; j++)
            {
                ttt+=topValue[i][j];
                if (realClockHands[i][j]!=0)
                {
                    return;
                }
            }
        }
        minAns=min(minAns,ttt);
    }
}

int solution(vector<vector<int>> clockHands) {
    //0=12, 1=3, 2=6, 3=9
    int sss=clockHands.size();
    vector<vector<int>> vvvv(sss,vector<int>(sss,0));
    Calc(sss, 0, vvvv, clockHands);
    
    return minAns;
}

 

---

맨 윗줄을 결정해 줌으로써 나머지를 풀 수 있는 문제였다.

처음에 완전 탐색을 해야하나 고민했지만, 하나만 기준을 잡고 결정해 주면 나머지는 빠르게 풀 수 있는 문제였다.

힌트를 보지 않았더라면 하루종일 고민 했어야 했을 것 같다...

프로그래머스