[Swift] 백준 17484_진우의 달 여행 (Small)

풀이 방법

 

1. 우주선이 어느 방향으로 나아갈 수 있는지(can move)

2. 우주선이 과거에서 어느 방향에서 왔는지 (prev move)

 

"우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다." 문장은 문제의 핵심 이었습니다. 그러면 어떻게? 이전 방향의 움직임을 체크할 수 있을까에 대해서 고민했습니다.

 

사고 과정은  다음과 같습니다.

 

먼저 우주선이 갈 수 있는 항로가 있습니다. 그항로는 아마 숫자들로 채워져 있을 것 입니다.

 

 

시간이 지남에 따라 우주선은 이동할 것이고 우리는 우주선의 이동경로를 체크해야 합니다. 다음과 같이 우주선의 이동경로를 저장했습니다.

 

우주선의 이동 경로는 A(북서쪽) B(북쪽) C(북동쪽)가 있습니다. 우주선이 북동쪽으로 이동하면 그 칸의 C에 값이 채워지게 됩니다. 그리고 우주선이 움직이면서 가장 최적의 경로를 DP를 통해서 계산하면 됩니다.

 

 

우주선이 나아갈 수 없는 조건은 다음과 같습니다.

• 격자칸의 ABC가 초기값 그대로 일 경우

   • row가 0을 제외한 arr[row][col]의 c는 절대 갈 수 없는 곳 입니다.

 

 

• 같은 방향으로는 못 나아감 A-> A, B->B C->C 불가

 

 

코드

import Foundation


let NM = readLine()!.split(separator: " ").map{Int($0)!}
let N = NM[0]
let M = NM[1]

var arr: [[Int]] = []
let steps: [[Int]] = [[1, -1], [1, 0], [1, 1]]

var t: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: -1, count: 3), count: M), count: N)
for _ in 0..<N {
  let input = readLine()!.split(separator: " ").map{Int($0)!}
  arr.append(input)
}

arr[0].enumerated().forEach{ (ind, val) in t[0][ind] = [val, val, val]}

func next(_ row: Int, _ col: Int, _ curInd: Int, _ toStepInd: Int) {
  let step = steps[toStepInd]
  let curRow = row + step[0]
  let curCol = col + step[1]
  
  if toStepInd == curInd || // 가려고 하는 방향이 현재 방향과 일치 할 때
      !arr.indices.contains(curRow) ||
      !arr[0].indices.contains(curCol) ||
      t[row][col][curInd] == -1 { // 현재 자리가 아무도 방문하지 않았을 때
    return
  }

  let prev = t[row][col][curInd]
  let curVal = prev + arr[curRow][curCol]
  let tVal = t[curRow][curCol][toStepInd]
  // 가려고 하는 자리가, 우주선이 처음 방문할 때
  if tVal == -1 {
    t[curRow][curCol][toStepInd] = curVal
  }else {
    t[curRow][curCol][toStepInd] = min(tVal, curVal)
  }
}


for i in 0..<N {
  for j in 0..<M {
    for k in 0..<3 {
      for stepInd in 0..<steps.count {
        next(i, j, k, stepInd)
      }
    }
  }
}


print(t[N - 1].flatMap{$0}.filter{$0 != -1}.min()!)