Lv.3 : 고고학 최고의 발견

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• N*N 행렬에서 모든 칸의 숫자(시계)를 0(12시방향)으로 만들어야 한다.
  • 0 : 12시, 1 : 3시, 2 : 6시, 3 : 9시
• 한 칸의 시계를 시계방향으로 돌릴 수 있고, 돌리면 상하좌우 인접한 시계도 함께 돌아간다.
• 모든 시계를 12시 방향으로 만드는 최소 조작 횟수를 출력한다.

🔸 문제 풀이 🔸

• 여러 경우의 수를 따져봐야 하는데, BruteForce는 O(64^4)이므로 너무 크다.
• Greedy 접근으로 풀이할 수 있다.
  • 시계를 조작하는 순서는 상관 없으므로 위쪽에서 아래쪽 행으로 조작하고자 한다.
  • 첫 행의 상태만 임의로 정하면, 다음 행은 위쪽 행을 0으로 만들기 위해 돌리면 된다.
  • 마지막 행까지 돌렸을 때 모두 0인 경우의 최소 조작 횟수를 구한다.
  • 첫 행만 모든 경우의 수를 따져보면 되므로 O(8^4)로 줄어든다.

---

🔸 코드 🔸

class Solution {
    private final int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 상 우 하 좌
    private int n;
    
    public int solution(int[][] clockHands) {
        
        int min = Integer.MAX_VALUE;
        n = clockHands.length;
        
        // Greedy
        for(int i = 0; i < (1 << (2*n)); i++) { // 첫 행 모든 경우의 수
            int[][] copy = deepCopy(clockHands);
            int cnt = 0;
            int temp = i;
            
            // 첫 행 조작
            for(int col = 0; col < n; col++) { // 오른쪽 부터 0~3 으로 돌려보기
                int rotateCnt = temp % 4;
                temp /= 4;
                cnt += rotateCnt;
                rotate(copy, 0, col, rotateCnt);
            }
            
            // 나머지 행 조작
            for(int row = 1; row < n; row++) {
                for(int col = 0; col < n; col++) {
                    int rotateCnt = (4 - copy[row-1][col]) % 4; // 바로 윗행 값을 0으로 만드는 회전수
                    cnt += rotateCnt;
                    rotate(copy, row, col, rotateCnt);
                }
            }
            
            // 마지막 행이 모두 0인지 확인
            boolean flag = true;
            for(int col = 0; col < n; col++) {
                if(copy[n-1][col] != 0)  {
                    flag = false;
                    break;
                }
            }
            if(flag) min = Math.min(min, cnt);
        }

        return min;
    }
    
    private void rotate(int[][] arr, int row, int col, int rotateCnt) {
        arr[row][col] = (arr[row][col] + rotateCnt) % 4; // 현재 좌표 돌림
        for(int[] d : dir) {
            int r = row + d[0];
            int c = col + d[1];
            if( 0 <= r && r < n && 0 <= c && c < n) {
                arr[r][c] = (arr[r][c] + rotateCnt) % 4; // 4방 좌표 돌림
            }
        }
    }
    
    private int[][] deepCopy(int[][] arr) {
        int[][] copy = new int[n][n];
        for(int i = 0; i < n; i++) {
            System.arraycopy(arr[i], 0, copy[i], 0, n);
        }
        return copy;
    }
}

🔸 코드 해석 🔸

• 첫 행의 경우의 수는 n칸을 0~3 숫자로 채우는 것이다.
  • 1부터 4^n까지 키워나가면 되는데, 1 << (2 * n)으로 4*n을 표현할 수 있다.
  • 4 모듈러 연산으로 n 번째부터 0번째 칸을 채울 수 있다.
  • 다음 칸을 채울 때는 4로 나눈 몫을 값으로 저장해 넘긴다.
• 첫 행의 각 경우의 수를 따져보기 위해 입력 받은 2차원 배열을 복사해야 한다.
  • 깊은 복사를 수행하는 deepCopy() 메서드를 만들어서 사용했다.
• 한 시계를 돌렸을 때, 인접 시계도 돌아가야 하므로 rotate() 메서드를 만들어 사용했다.
• 첫 행을 제외한 나머지 행이 각각 위쪽 행의 값을 모두 0으로 만들도록 조작한다.
• 마지막 행까지 모두 0이 된 경우에서 조작 횟수의 최솟값을 기록한다.

---

🔸 end 🔸

• 상당히 어렵게 다가온 문제이다. 처음엔 문제 분석과 풀이 전략을 적어가며 시간을 보냈고, 그리디를 선택했지만 방법이 틀려서 테스트1, 테스트2를 제외하고 시간초과가 났었다.

/*
< 문제 정리 >
  - N*N 행렬에 시계들이 채워있음 (N : clockHands의 길이)
  - 시계는 상하좌우 4방향 (12시부터 시계방향 0,1,2,3)
  - 최소 조작으로 모든 방향이 0이 되도록 하기

< 풀이 계획 >
1) 알고리즘
    - DFS
        - 행렬의 상태 저장이 필요하므로 DFS 어떤가
        - 그럼 깊이의 최대는? -> 가늠할 수 없는 것 같으니 포기
    - 그리디**
        - 돌렸을 때 12시가 되는 바늘이 많으면 +1, 주변에 0 개수는 -1
    - BFS
        - 방문체크를 2차원 배열로?
        - 최대 64칸을 4가지 경우의수 : 4^64 = 너무큼
    - 역방향 탐색
        - 모두 12시 상태에서 기존 상태 만들기
        - 잘 모르겠음
    - 그리디 ---- 정답 풀이 2개맞고 나머지 시간초과 나서 풀이 봄
        - >> 조작 순서가 중요하지 않으므로 규칙을 정해 한 방향으로 조작하면 됨 <<
        - 위에 첫 행을 임의조작하고, 다음 행에서 윗 줄이 0이 되도록 조작
        - 마지막 행까지 완료했을 때 모두 0이 됐는지 확인
        - 첫 행의 경우의 수만 따지면 되므로, 브루트포스 4^64에서 -> 그리디 4^8로 줄어듦
        
2) 메서드
    - 일단 돌리는건 1회당 시계방향 1칸
    - 인접한 인덱스도 회전 하는 기능 필요
*/

• 결국 풀이 전략 힌트를 봤지만, 첫 행의 경우의 수를 어떻게 해야할 지 몰라서 정답 코드까지 보고 클론 코딩 하듯 풀이를 제출했다.
• 이 문제의 핵심 풀이 요소는 조작 순서가 상관 없으므로 한 방향으로 일정하게 돌리면 된다는 것이다.
  • 위 풀이에서도 첫 행의 상태를 만들 때 n-1번부터 0번 인덱스 까지 값을 채워나가며 돌렸고,
    그 다음은 행을 1~n-1 까지 이동하며 값을 채워 나갔다.
• 첫 행의 상태를 만들때 비트 연산과 모듈러 연산을 기가막히게 사용한걸 보고 감탄했다.
• 여러모로 배운게 많은 문제였던 것 같다.