[JS] 고고학 최고의 발견

문제만 놓고 보면 완전탐색 문제같아 보인다.

 

실제로 모든 케이스를 검사한다고 생각한다면...

 

들어올수 있는칸이 64칸이므로 4 ^ 64 즉 절대로 시간안에 풀 수 없는 경우의 수가 나온다.

 

 

문제를 약간 생각해본다면 위 경우의 수를 획기적으로 줄일 수 있다.

 

만약에 퍼즐의 맨 윗칸이 고정되어 있다고 생각해보자. 

 

01030213 <== 이런식으로 맨 윗줄을 고정해둔다고 생각해두면, 해당 줄을 00000000으로 만들기 위해서는 반드시 그 아래의 시계를 돌려야 한다.

 

시계가 십자모양이므로 한줄이 고정된다면 그 줄을 바꾸기 위해서는 해당 시계의 아래에 있는 시계로만 동작이 가능하기 때문이다.

 

 

 

 

위 경우에서 맨 윗줄이 ↑←←↑ 로 고정되어 있다고 생각해보자.

 

두번째 ← 를 바꾸기 위해서는 노란색으로 색칠되어 있는 ↓ 말고는 제어할 수가 없다.

 

 

같은 방식으로 첫줄,두번째줄... 진행한다면 첫줄에 의해서 나머지 줄들이 정해지게 된다.

 

 

따라서 모든 경우의수를 따지는 것이 아닌 첫 줄의 경우의 수만 줄이면 되므로

 

4 ^ 8 의 경우의 수만 따져주면 된다.

 

 

필자가 문제를 푼 방법은 아래와 같다.

 

1. 지도에서 시계까 회전하는 함수를 구현

2. 첫줄이 고정되었다고 가정하고 시계를 돌렸을때 해결할 수 있는지 유무를 확인하는 함수를 구현

 -> 해결할 수 없다면 false 반환

 -> 해결할 수 있다면 돌린 횟수를 반환

 

3. 첫줄을 dfs를 활용해서 4가지 케이스씩 4^n의 케이스를 돌려가면서 확인

4. 나온 값들 중 가장 작은 값을 반환

 

 

 

function solution(clockHands) {
    const len = clockHands.length
    const dc = [0,1,0,-1,0]
    const dr = [0,0,1,0,-1]
    
    const change = (r,c,map) => {
        for (let k = 0 ; k < 5 ; k++){
            const [nr,nc] = [r + dr[k] , c + dc[k]]
            if (0<= nr && nr<len && 0<= nc && nc < len){
                map[nr][nc] = (map[nr][nc] + 1) % 4
            }
        }
    }
    
    const checkMap = (map) => {
        const tmpMap = map.map(v => [...v])
        let ret = 0
        for (let i = 1 ; i < len ; i ++){
            for (let j = 0 ; j < len ; j++){
                const maxK = (4 - tmpMap[i-1][j])%4
                for (let k = 0 ; k < maxK ; k++){
                    change(i,j,tmpMap)
                    ret ++
                }
            }
        }
        
        for (let i = 0 ; i < len ; i++){
            for (let j = 0 ; j < len ; j++){
                if(tmpMap[i][j]) return false
            }
        } 
        return ret
    }
    
    const retAry = []
    const dfs = (n,cnt) =>{
        if (n===len) {
            const ret = checkMap(clockHands)
            
            if (ret!==false) retAry.push(ret + cnt) 
            return
        }
        
        for (let i = 0 ; i <4 ; i++){
            dfs(n+1,cnt+i)
            change(0,n,clockHands)
        }
    }
    dfs(0,0)
    return Math.min(...retAry)
}