[프로그래머스] Swift - 고고학 최고의 발견

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

프로그래머스

 

2024.01.19 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 2차원 배열인 clockHands가 주어집니다.
• 배열의 각 칸에는 0부터 3까지의 정수 중 하나가 들어있습니다.
• 이 퍼즐을 열기 위해서는 모든 칸이 0이되어야 합니다.
• 0~3까지의 숫자는 시계의 방향을 의미합니다.
  • 0: 12시, 1: 3시, 2: 6시, 3: 9시
• 조작 1회로 시곗바늘을 시계 방향으로 90도씩 돌릴 수 있으며 돌릴 때 상하좌우로 인접한 시계들의 시곗바늘도 함께 돌아갑니다.
• 모든 칸이 12시를 가리키게 할 때 필요한 최소 조작 횟수를 리턴해야 합니다.

 

 

우선 시계의 특성 상 4번 이상 같은 칸을 돌리는 것은 무의미합니다. -> 한 바퀴를 돌아 다시 원래 상태로 돌아오기 때문!

 

제한 사항에 따라 clockHands의 크기는 최대 8까지로 크지 않은 수입니다.

그렇다고 해서 각 칸을 90도씩 한바퀴 돌린 모든 경우의 수는 너무 많습니다.

크기가 8인 시계라면 4^64개의 경우의 수가 나오기 때문에 이걸 전부 탐색하는 것은 불가능합니다.

 

여기서 아이디어가 필요했습니다.

 

문제 조건에 따라 특정 칸을 돌리게 되면 상하좌우로 인접한 칸들도 같이 돌아가게 되는데,

만약 a 위치의 칸을 돌리게 되면 a보다 한칸 위의 칸에도 영향을 주게 된다는 의미입니다.

 

즉, a는 a보다 한칸 위의 칸이 0이 되도록 돌리는 횟수를 정해야 합니다.

 

정리해 보면

1. 시계를 0번째 행부터 아래 방향으로 차례로 돌려 나갑니다.
2. 현재 대상 칸의 회전 횟수는 대상 칸의 한 칸 위의 숫자가 0이 되도록 하는 횟수입니다.
3. 이렇게 마지막 행까지 다 돌리게 된다면 마지막 행을 제외한 0~n-2 행까지는 전부 0이 되어 있을 것입니다.
4. 이 때 마지막 행을 검사해서 전부 0인 케이스였다면 결과 값을 갱신하면 됩니다.

이 순서로 작업을 진행하면 되는데 문제는 첫 번째 행의 경우입니다.

 

두 번째 행부터는 돌려야 하는 횟수가 윗 칸의 수에 맞추어 돌려주면 되는데 첫 번째 행은 윗 칸이 없기 때문에 첫 번째 행에 대해서는 각 칸의 모든 회전 경우의 수를 구해줘야 합니다.

이는 4^n (n은 8이하)이기 때문에 충분히 감당 가능한 연산 횟수입니다.

 

즉, 첫 번째 행에 대해서는 모든 경우의 수 탐색 (DFS 사용)

각 경우의 수에 대해 행을 1씩 증가시키며 자신의 윗 행을 0으로 만들고 만약 마지막 행까지 전부 0이 되었다면 결과 값을 갱신하는 방식으로 구현했습니다.

 

 

풀이

1. canOpen 함수 구현

// 마지막 행이 전부 0으로 변했는지 확인
fileprivate func canOpen(clock: [[Int]]) -> Bool {
    let lastRow = clock.count - 1
    
    for y in clock[0].indices {
        if clock[lastRow][y] != 0 {
            return false
        }
    }
    
    return true
}

 

퍼즐(시계)의 마지막 행이 전부 0이면 퍼즐을 푼 상태로 판단합니다.

(0번째 행부터 차례로 0으로 만들었기 때문에 마지막 행만 검사하면 됨!)

 

 

2. rotate 함수 구현

fileprivate func rotate(clock: [[Int]], x: Int, y: Int, rotateCnt: Int) -> [[Int]] {
    var newClock = clock
    let dx = [0, 0, 0, 1, -1]
    let dy = [0, 1, -1, 0, 0]
    let size = clock.count
    
    for i in 0..<5 {
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        if nx >= 0 && nx < size && ny >= 0 && ny < size {
            newClock[nx][ny] = (newClock[nx][ny] + rotateCnt) % 4
        }
    }
    
    return newClock
}

 

(x, y) 위치를 rotateCnt만큼 회전시키는 함수입니다.

(x, y) 위치 뿐만 아니라 인접 상하좌우 칸도 회전하게 됩니다.

 

 

3.  calculateTotalRotateCnt 함수 구현

// 임의의 첫 번째 행 상태에서 이후 행들 조작
fileprivate func calculateTotalRotateCnt(clock: [[Int]], startCnt: Int) -> Int? {
    var result = startCnt
    var clock = clock
    
    for x in 1..<clock.count {
        for y in 0..<clock[0].count {
            let upper = clock[x-1][y] // 현재 위치의 바로 위의 칸
            let needToRotateCnt = (4 - upper) % 4
            clock = rotate(clock: clock, x: x, y: y, rotateCnt: needToRotateCnt)
            result += needToRotateCnt
        }
    }

    return canOpen(clock: clock) ? result : nil
}

 

임의의 첫 번째 행 상태를 받아서 나머지 행들을 돌리고 최종 회전 횟수를 리턴하는 함수입니다.

자신보다 윗 칸이 0이되도록 needToRotateCnt를 설정합니다.

 

최종 결과 clock이 퍼즐을 열 수 없는 상태, 즉, 마지막 행에 0이 아닌 수가 있는 상태라면 nil을 리턴합니다.

 

4. solution 함수 구현

fileprivate func solution(_ clockHands:[[Int]]) -> Int {
    var result = Int.max
    
    // 첫 번째 행의 모든 경우의 수 탐색
    func dfs(y: Int, cnt: Int, clock: [[Int]]) {
        if y == clock.count {
            if let totalCnt = calculateTotalRotateCnt(clock: clock, startCnt: cnt) {
                result = min(result, totalCnt)
            }
            return
        }
        
        let rotateCases = [0, 1, 2, 3]
        
        for c in rotateCases {
            let newClock = rotate(clock: clock, x: 0, y: y, rotateCnt: c)
            
            dfs(y: y+1, cnt: cnt+c, clock: newClock)
        }
    }
    
    dfs(y: 0, cnt: 0, clock: clockHands)

    return result
}

 

dfs 를 통해 첫 번째 행의 상태의 모든 경우의 수를 구합니다.

각 경우의 수에서 calculateTotalRotateCnt 함수를 호출하여 마지막 행까지 회전시켰을 때 총 회전 횟수를 구합니다.

이 값이 nil이 아니라면 정답의 후보가 됩니다.

➡️ result를 갱신

 

 

 

마무리

첫 번째 행만 모든 경우의 수를 구하고 나머지 행부터는 자신의 윗 칸을 0으로 만들기 위한 횟수 만을 계산하면 된다는 아이디어가 필요했습니다.

 

그 이후의 구현 과정은 어렵지 않았지만 이 아이디어를 생각해내는 것이 어려워서 저도 다른 분들이 올려주신 힌트를 참고해서 풀었습니다.