[백준/Swift] 1890: 점프 | PS일지

문제

1890번: 점프

간단한 문제 요약

n*n의 게임판 가장 왼쪽 위에서부터 시작해서 게임판의 숫자만큼 오른쪽 또는 아래칸으로 점프할 수 있다. 점프할 때 방향 바꿀 순 없다. (0,0)에서 출발해서 (n-1,n-1)까지 가는 모든 경우의 수를 구하시오!!

문제 풀이,  느낀점

 

typealias Point = (x:Int, y:Int)
let direction = [(0,1),(1,0)]
var n = Int(readLine()!)!
var ans = 0
var graph = Array(repeating: [Int](), count: n)

_=(0..<n).map{
  graph[$0] = readLine()!.split(separator: " ").map{Int(String($0))!}
}

 

맵의 크기가 최악의 경우 100*100 밖에 되지 않아서 빼박 bfs구나!! 맵의 정보를 입력받고, 코드를 구현했다 메모리초과가 발생했습니다. 음,, 크기도 작은데 + bfs로 아래 or 오른쪽으로만 이동하는데 왜 메모리 초과가 발생하는지 의문입니다...

 

func isOutOfBounds(p: Point) -> Bool {
  return p.x<0 || p.y<0 || p.x > n - 1 || p.y > n - 1
}

func bfs() {
  var queue = [(0,0)]
  var idx = 0
  while idx < queue.count {
    let (cx,cy) = queue[idx]
    idx += 1
    let mul = graph[cy][cx]
    if cx == n-1 && cy == n-1 {
      ans += 1
      continue
    }
    for (dx,dy) in direction {
      let (nx,ny) = (cx+dx*mul,cy+dy*mul)
      if isOutOfBounds(p: (nx,ny)) { continue }
      queue.append((nx,ny))
    }
  }
  print(ans)
}

 

그런데 한 가지 예상했던 것은 초반에 맵을 탐색해 나갈 때 중간 지점을 거쳐 끝까지 도착한다 한들 이 정보를 이용하지 못하고 계속해서 반복으로 특정 구간을 거쳐간다는 점? 그렇다면 메모제이션을 사용해야 메모리 초과를 해결할 수 있습니다. cache[0][0]를 1로 두고, 이차원 탐색을 통해 순차적으로 맵을 탐색해 가면서 각각의 칸에 대해서 오른쪽 또는 아래로 갈 수 있는 경우를 한 개씩 더해가며 구해가는 것입니다. 특정 A칸에서는 (0,0)에서부터 특정 A칸까지 갈 수 있는 경우가 더해집니다.

 

메모리초과 측정을 못했는데,, 관련해서 더 찾아봐야겠습니다..

코드

var graph = Array(repeating: [Int](), count: n)
_=(0..<n).map{
  graph[$0] = readLine()!.split(separator: " ").map{Int(String($0))!}
}
func solution() {
  var cache = Array(repeating: Array(repeating: 0, count: n), count: n)
  cache[0][0] = 1 // 시작을 1로합니다.
  for y in 0..<n {
    for x in 0..<n where graph[y][x] != 0 {
    // 특정 좌표 (x,y)일 때 갈 수 있는 오른쪽,  or 아래에 대한 좌표를 구합니다.
      let nx = x + graph[y][x]
      let ny = y + graph[y][x]
      // 만약 맵의 범위를 넘지 않는다면~
      if ny<n { cache[ny][x] += cache[y][x] }
      if nx<n { cache[y][nx] += cache[y][x] }
    }
  }
  print(cache[n-1].last!)
}
solution()