코딩테스트 -- 고고학 최고의 발견 - (프로그래머스 / C++)

 

프로그래머스

 

 

문제요약!

---

n*n 배열의 각 칸에 상하좌우로 시곗바늘이 각 방향을 가지고 배치되어있는 퍼즐이 있다고 합니다.

 

시곗바늘은 다음과 같은 조건을 가지고 회전가능합니다.

1. 시계방향으로 회전가능

2. 돌린 칸의 상하좌우 칸의 시곗바늘도 같이 회전

 

위와 같은 조건을 지키며

모든 칸의 시곗바늘을 12시로 만들수 있는 최소의 조작횟수를 구하는 문제!

 

---

 

 

처음에는 단순히 탐색을 통해 모든 경우의 수를 구해주려 했으나,

n이 8일 경우 64칸의 모든 경우의수...까지는 계산하기에 무리가 있어 보였습니다.

 

 

그래서 먼저 가장 위 오른쪽 시곗바늘 부터 회전시켜보며 경우의 수를 생각해 보았습니다.

 

탐색의 방향은 일단 아래처럼 진행한다고 가정하겠습니다.

 

 

가장 상단의 왼쪽 칸을 1번칸이라고할때

1번칸을 회전시키는 경우는 

0번, 1번, 2번, 3번 회전시키는 4가지 경우로 나뉩니다. 

 

마찬가지로 2번째 칸, 3번째칸... 가장 상단의 칸들을 모두 동일한 경우의 수를 가집니다. 

 

 

여기까지는 일반적인 탐색으로 진행한후

 

다음줄을 생각해 보았습니다. 

 

두번째줄을 회전시킬때에는 첫째줄과는 약간 다른 점이 있습니다. 

바로 현재 위치한 칸의 바로 윗칸의 값을 12시 방향으로 맞춰줘야한다는 점

 

==>> 여기서 12시 방향으로 맞춰주지 않을 경우!

윗칸의 방향에 영향을 끼칠 칸이 더 존재하지 않기 때문! 

 

 

 

 

12시로 맞춰주지않을 경우 더이상의 탐색은 의미가 없기에 탐색에서 제외시켜줄 수 있습니다!

 

 

여기까지를 토대로 코드를 작성해 보았습니다.

 

 

 

 

 

 

그럼 코드!

---

vector<vector<int>> SaveclockHands;
vector<int> stateSave(5,0);

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

int answer = 987654321;
int n = 0;


int solution(vector<vector<int>> clockHands) {

    n = clockHands.size();

    SaveclockHands = vector<vector<int>>(n + 2, vector<int>(n + 2));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            SaveclockHands[i + 1][j + 1] = clockHands[i][j]; // 회전을 위한 편의성 벡터 생성
        }
    }

    dfs(1, 1, 0, SaveclockHands);

    return answer;
}

 

먼저 기본 변수들과 회전을 도와줄 편의성 벡터 SaveclockHands를 생성해주었습니다.

 

==> clockhands에서 회전을 할때 모서리부근의 칸들을 회전시킬때 범위를 넘어가는 부분을 처리해야하는데

이를 미리 처리하기위한, 각 행,열의 길이가 +2 처리해준 벡터!

 

 

 

그리고 탐색함수를 구성해주었습니다.

void dfs(int y,int x, int count, vector < vector<int>>SaveclockHandsList) {//

    // 좌표 설정 및 몇번돌릴지 결정
    if (y == n+1) { // 탐색 도달 끝!
        //cout << "--------"<<count<<"------ - " << endl;
        
        for (int i = 1; i < n + 1; i++) {
            if (SaveclockHandsList[n][i] != 0) {
                return;
            }
        }

        answer = min(answer, count);
        return;
    }

    if (x == n + 1) { // 행의 끝 도달 처리
        dfs(y + 1, 1, count, SaveclockHandsList);
        return;
    }

 

탐색함수도 먼저 예외들을 처리해주었습니다. 

 

if(x==n+1) 부분은 각 행의 끝에 도달하였을때 다음 행으로 이동하기위한 부분!

 

if(y==n+1) 부분은 배열의 끝 행에 도달하였기에 그 지점에서 탐색을 종료하고,

마지막 행들의 값들이 12시로 맞춰졌는지 확인하도록 구성하였습니다.

 

 

다음은 첫행일시 처리하는 부분입니다.

if (y == 1) { // 첫행 고려할 것 없이 회전 시키기 가능

        for (int i = 0; i < 4; i++) { // 시계방향 회전
            
            for (int j = 0; j < 5; j++) { //각 방향으로
                int minusCal=(SaveclockHandsList[y + dy[j]][x + dx[j]] + i)%4;
                SaveclockHandsList[y + dy[j]][x + dx[j]] = minusCal;
            }

            dfs(y, x + 1, count + i, SaveclockHandsList); //

            for (int j = 0; j < 5; j++) { // 원상태
                int minusCal = (SaveclockHandsList[y + dy[j]][x + dx[j]]+4 - i)%4;
                SaveclockHandsList[y + dy[j]][x + dx[j]] = minusCal;
            }
        }
    }

 

여기까지는 일반적인 탐색으로 4방향의 칸들을 4가지의 경우로 모든 부분을 탐색하며 지나갑니다.

 

 

 

 

그리고 마지막으로 두번째 행부터는 현재칸의 바로 윗칸을 12시로 맞춰주며 이동하는 부분입니다.  

 

여기서 4가지 경우가 아닌 무조건 윗칸의 남은 회전수,

즉 1가지의 경우로 계산하며 탐색해나가기에 시간초과 나지 않고 통과할 수 있었습니다.  

else { // 윗줄에 남은 횟수를 모두 탕진해야함
        int remainNum = 0; // 윗칸에 있는 수
        int minusCal=0;

        remainNum = (4 - SaveclockHandsList[y - 1][x])%4;
        
        if (remainNum != 0) {
            for (int i = 0; i < 5; i++) { //각 방향
                minusCal = (SaveclockHandsList[y + dy[i]][x + dx[i]] + remainNum) % 4;
                SaveclockHandsList[y + dy[i]][x + dx[i]] = minusCal;
            }
        }
        
        dfs(y, x + 1, count + remainNum, SaveclockHandsList);
    }

 

 

 

여기까지가 일단 끝! 

하지만 위의 코드의 경우 dfs탐색에

SaveclockHandsList벡터를 계속해서 넘겨주는것이 처리 시간에 문제를 주는듯 합니다...

 

 

 

 

처리 시간 까지 생각하여 설계한다면 아래와 같이 코드를 생성할 수 있을것 같습니다.

프로그래머스

 

 

 

 

더 최적화된 코드도 있었지만 아직 이해가 안되서... 일단 보류! 

 

첫째줄만 완전탐색하고 아랫줄 부터는 정해진 값에 의해 탐색이 아닌 계산을 하게 된다는 점을 이용한다면,

푸는데에는 그렇게 어렵지만은 않은 문제였습니다. 

 

 

 

 

틀린점이 있다면 댓 달아주세요!