[프로그래머스] 숫자 타자 대회 (Swift)

https://school.programmers.co.kr/learn/courses/30/lessons/136797?language=swift

프로그래머스

 

DP+DFS

 

숫자 키패드가 있고, 손가락이 놓인 곳에서 이동하지 않고 누를 때는 시간 1초 소요, 인접한 상하좌우로 이동할 땐 시간 2초 소요, 인접한 대각선으로 이동할땐 3초 소요된다고 할 때

입력으로 받은 숫자들을 모두 누르는 최소 시간을 구하는 문제

* 처음시작할 때 양손가락은 4, 6에 각각 위치하며

* 같은 번호를 양손가락이 모두 누르고 있을 수는 없다.

 

접근방법

1. 우선, 0~9까지의 번호판이 서로에게 가는 모든 경우의 최단거리를 구해놓아야 한다. (10*10 배열) -> 이걸 BFS식으로 구해볼까 생각했는데 실패해서 그냥 하드코딩함 (weight 배열)

2. 처음위치 (4,6)에서 시작해서 번호 한개씩 순서대로 누를 때, 왼손을 사용할 때와 오른손을 사용할 때 모두 소요되는 시간을 구한다.

아래 그림 처럼 완전탐색해야하는데, 이 과정에서 눌러야될 번호가 길어질 수록 같은 레벨 (아래 그림에서 같은 열) 에서 중복되는 경우가 생긴다. -> 이걸 반복해서 구하지말고 DP로 저장해두고 쓰자는 방법

DP로 풀어야하는 이유..

 

다들 재귀로 풀길래 다르게 풀어보려다가 결국 포기하고 재귀로 풀었음

재귀는 참..코드는 간단해지는데 머리는 복잡해짐

idx는 내가 지금 눌러야하는 (아직 누르지 않은 인덱스 번호다)

left는 현재 왼손이 누르고 있는 번호, right은 현재 오른손이 누르고 있는 번호

그래서 dp는 결국 현재 위치에서 시작해서 끝까지 번호를 누를 경우 최소 시간을 담고 있는 것이 된다.

아, 보통 DP를 사용할 때, 처음부터 현재위치까지의 결과 값을 저장하는 경우가 많은데

여기서는 현재위치부터 마지막까지의 결과값을 저장하는거라 헷갈렸나보다.

 

 

소스코드

import Foundation

func solution(_ numbers:String) -> Int {
    
    let number:[Int] = Array(numbers).map { Int(String($0)) ?? 0 }
    
    let weight = [
      [1, 7, 6, 7, 5, 4, 5, 3, 2, 3],
      [7, 1, 2, 4, 2, 3, 5, 4, 5, 6],
      [6, 2, 1, 2, 3, 2, 3, 5, 4, 5],
      [7, 4, 2, 1, 5, 3, 2, 6, 5, 4],
      [5, 2, 3, 5, 1, 2, 4, 2, 3, 5],
      [4, 3, 2, 3, 2, 1, 2, 3, 2, 3],
      [5, 5, 3, 2, 4, 2, 1, 5, 3, 2],
      [3, 4, 5, 6, 2, 3, 5, 1, 2, 4],
      [2, 5, 4, 5, 3, 2, 3, 2, 1, 2],
      [3, 6, 5, 4, 5, 3, 2, 4, 2, 1],
    ]
    
    var dp:[[[Int]]] = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: -1, count: 10), count: 10), count: number.count+1)
    
    func recur(_ idx: Int, _ left: Int, _ right: Int) -> Int {
        if idx == number.count {
            return 0
        }
        if dp[idx][left][right] != -1 {
            return dp[idx][left][right]
        } 
        let num = number[idx]
        
        var result = Int.max
        // 왼손 이동
        if right != num {
            result = min(result, weight[left][num] + recur(idx+1, num, right))
        }
        // 오른손 이동
        if left != num {
            result = min(result, weight[right][num] + recur(idx+1, left, num))  
        }
        dp[idx][left][right] = result
        
        return dp[idx][left][right]
    }
    
    return recur(0,4,6)
}