프로그래머스 [Lv. 3] 고고학 최고의 발견 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(clockHands) {
    let answer = Infinity;
    const n = clockHands.length;
    const isValid = (nr, nc) => 0 <= nr && nr < n && 0 <= nc && nc < n;
    const dr = [0, 0, 1, 0, -1];
    const dc = [0, 1, 0, -1, 0];
    
    const turning = (r, c, copyClock, turn) => {
        for (let d = 0; d < 5; d++) {
            const nr = r + dr[d];
            const nc = c + dc[d];
            if (isValid(nr, nc)) {
                copyClock[nr][nc] = (copyClock[nr][nc] + turn) % 4;
            }
        }
    }
    
    const dfs = (s, visited, vCnt) => {
        if (vCnt >= answer) {
            return;
        }
        if (s === n) {
            // 첫 번 째 행 회전시키기
            let cnt = vCnt;
            const copyClock = clockHands.map((e) => e.slice());
            for (let c = 0; c < n; c++) {
                let tmpCnt = visited[c];
                if (tmpCnt) {
                    turning(0, c, copyClock, tmpCnt);
                }
                
            }
            for (let r = 1; r < n; r++) {
                for (let c = 0; c < n; c++) {
                    // 위를 0으로 맞추기
                    const turn = (4 - copyClock[r-1][c]) % 4;
                    if (turn) {
                        cnt += turn;
                        turning(r, c, copyClock, turn);
                    }
                }
            }
            if (copyClock.at(-1).every((e) => e === 0)) {
                if (answer > cnt) {
                    answer = cnt;
                }
            }
            return;
        }
        for (let turn = 0; turn < 4; turn++) {
            dfs(s+1, [...visited, turn], vCnt+turn);
        }
    }
    dfs(0, [], 0);
    return answer;
}

풀이 방법

1. 0번째 행을 먼저 회전 시키고 1번째 행부터는 바로 위 행의 요소들을 0으로 맞춰가면 된다.
2. 조합을 먼저 만든다.
   1. 0번째 행의 요소 하나하나를 몇 번 돌릴지 조합을 만든다.
   2. 예를 들어 모든 요소를 돌리지 않을 경우 [0, 0, 0, 0]
   3. 모든 요소를 3번씩 돌릴 경우 [3, 3, 3, 3]
   4. 4번 이상은 돌려도 처음으로 돌아오기 때문에 1, 2, 3중에 하나로 조합을 만든다.
3. 조합이 만들어진 visited를 바탕으로 0번째 행의 모든 요소를 각각의 회전 수에 맞춰서 회전 시킨다.
   1. 회전 시킬 때 좌우하가 같이 움직이므로 turning 함수를 만들어서 상하좌우 + 현위치를 모두 회전시킨다.
4. 1번째 행부터는 바로 위를 0으로 맞출 회전수를 구한 뒤 위와 동일하게 모든 방향을 회전시킨다.
5. 마지막 행에서 모든 요소가 0이 되었다면 이 퍼즐을 풀었으므로 전체 회전수와 결과 값을 비교해서 최소값으로 갱신한다.
6. 0번째 행을 회전시킬 때 결과값보다 크거나 같다면 1번째 행부터 회전시키는 행위를 할 필요가 없다.
   1. 즉 vCnt를 만들어서 가지치기를 해봤는데 효과는 확실했다.

느낀점

• 이걸 조합과 완전탐색이라고 해야할지...
• 일단 파이썬으로 다시 풀어보면 좋을 것 같다.
• 솔직히 처음에는 dfs돌리면 불가능하겠다고 생각을 했는데 처음 행만 조합을 만들면 된다는 것을 깨달았다.