[javascript] 프로그래머스 level 3 - 고고학 최고의 발견

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

프로그래머스

 

문제 설명 

고고학자인 혜선은 오래전부터 성궤의 행방을 추적해왔습니다. 그동안 그의 연구는 주류 학자들로부터 인정받지 못했었지만, 혜선이는 포기하지 않고 조사를 계속했고 마침내 성궤의 행방을 알아내었습니다.

그러나 오래전 누군가로부터 봉인된 성궤는 특별한 잠금장치에 의해 보호되고 있었습니다. 잠금장치는 일종의 퍼즐과 연결되어 퍼즐을 해결하면 열리는 것으로 보입니다.

퍼즐은 시계들이 행렬을 이루는 구조물인데 하나의 시계에 시곗바늘은 하나씩만 있습니다. 각 시곗바늘은 시계방향으로만 돌릴 수 있고 한 번의 조작으로 90도씩 돌릴 수 있습니다. 시계들은 기계장치에 의해 연결되어 있어 어떤 시계의 시곗바늘을 돌리면 그 시계의 상하좌우로 인접한 시계들의 시곗바늘도 함께 돌아갑니다. 행렬의 모서리에 위치한 시계의 시곗바늘을 돌리는 경우에는 인접한 세 시계의 시곗바늘들이 함께 돌아가며, 꼭짓점에 위치한 시계의 시곗바늘을 돌리는 경우에는 인접한 두 시계의 시곗바늘들이 함께 돌아갑니다.

각 시계는 12시, 3시, 6시, 9시 방향 중의 한 방향을 가리키고 있습니다. 각 시계의 시곗바늘을 적절히 조작하여 모든 시곗바늘이 12시 방향을 가리키면 퍼즐이 해결되어 성궤를 봉인하고 있는 잠금장치가 열릴 것입니다.

노후화된 퍼즐 기계장치가 걱정되었던 혜선은 가능한 최소한의 조작으로 퍼즐을 해결하려고 합니다. 시곗바늘들의 행렬 clockHands가 매개변수로 주어질 때, 퍼즐을 해결하기 위한 최소한의 조작 횟수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 2 ≤ clockHands의 길이 ≤ 8
• clockHands는 2차원 배열이며 행과 열의 크기가 동일합니다.
• 0 ≤ clockHands의 원소 ≤ 3
• clockHands[i]의 원소들은 시곗바늘의 방향을 나타내며 0은 12시 방향, 1은 3시 방향, 2는 6시 방향, 3은 9시 방향을 나타냅니다.
• 해결 가능한 퍼즐만 주어집니다.

---

문제 풀면서 어려웠던 점

- 일단 규칙을 찾는 것 자체가 너무 어려웠다. (그러나 이런 종류의 문제는 한 번 풀어보면 다음부터는 규칙 찾기 쉬울 것 같음)

 

- 그리고 첫번째 줄에서 모든 경우의 수를 구하여야 하는데, 모든 경우의 수를 구하는 코드를 작성하는 것이 어려웠다. (이 경우 코테 많이 풀어보면서 그냥 계속 연습해봐야 할 것 같다.)

 

- getCount함수에서 뒤집는 횟수를 더해야 하는데 잘못하고, 윗 줄에서 0이 아닌 원소의 개수를 더해버려서 그 부분에서 계속 오류가 났다. 우연하게도 테스트 케이스에서는 오류가 안나서 계속 헤맸다.

 

문제 해결 방법

1. 첫번째 줄의 가능한 모든 경우의 수를 구한다.

1-1. 배열과 x인덱스, 뒤집은 횟수를 입력받는 함수 dfs(arr, x, count)

1-2. x인덱스에서 0번 뒤집기, 1번 뒤집기, 2번 뒤집기, 3번 뒤집기한 경우를 모두 구하여 dfs(arr,x+1,count+)를 다시 호출한다.

1-3. x가 주어진 배열의 가로길이와 같다면 그 후부터는 다음 줄로 넘어간다.

2. 두번째 줄부터는 뒤집는 방법이 정해져있다.

3. 이전 줄에서 0이 아닌 원소가 있는 인덱스를 해당 줄에서 뒤집는다. ex) arr[y-1][x] = 1 이면 arr[y][x]에서 뒤집어 줘야 함

4. 배열 끝까지 반복한다.

5. 마지막 줄에서 모두 0이 되고, answer보다 count값이 작다면 answer를 count값으로 갱신해준다.

---

코드

function solution(clockHands) {
    const length = clockHands.length
    let answer = Infinity;
    
    // 행에 0이 아닌 수가 있는지 확인
    const checkLine = (arr) => {
        const notZero = []
        arr.forEach((e,i) => {
            if(e !== 0) notZero.push(i)
        })
        return notZero
    }
    
    const turn = (value ,num) => {
        return value + num > 3 ? value + num - 4 : value + num
    }
    
    // 시계 돌리기
    const turnClock = (arr,y,x,num) => {
        arr[y][x] = turn(arr[y][x], num)
        if(y-1 >= 0) arr[y-1][x] = turn(arr[y-1][x], num)
        if(y+1 < length) arr[y+1][x] = turn(arr[y+1][x], num)
        if(x-1 >= 0) arr[y][x-1] = turn(arr[y][x-1], num)
        if(x+1 < length) arr[y][x+1] = turn(arr[y][x+1], num)
    }
    
    // 첫번째 줄 정해지고, 나머지 count 구하기
    const getCount = (arr, count) => {
        for(let i = 0; i < length - 1; i++) {
            const tmp = checkLine(arr[i])
            if(tmp.length > 0) {
                tmp.forEach(e => {
                    count += 4 - arr[i][e]
                    turnClock(arr, i+1, e, 4 - arr[i][e])
                })
            }
            if(count > answer) break
        }
        if(checkLine(arr[length-1]).length === 0 && count < answer) answer = count
    }
    
    const dfs = (arr, x, count) => {
        if(x === length) return getCount(arr, count)
        for(let num = 0; num < 4; num++) {
            const newArr = arr.map(e=>[...e])
            turnClock(newArr, 0, x, num)
            dfs(newArr, x+1, count+num)
        }
    }
    dfs(clockHands,0,0)
    return answer;
}

 

---

배운 점

- 이런 뒤집어서 모두 같은 문양으로 만드는 문제는 보면 첫번째 줄만 완전 탐색하고 그 이후는 규칙이 존재하기 때문에 의외로 간단한 것 같다.(소마 코테에서 비슷한 류의 문제가 나왔고 그때도 풀이방법은 이와 같았다. 첫번째 줄만 DP적용하고 밑 줄은 규칙대로 진행함)