[알고리즘] Swift -백준 #11048(이동하기) -DP

문제링크

https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

예제 입력 1 

3 4
1 2 3 4
0 0 0 5
9 8 7 6

예제 출력 1 

31

예제 입력 2 

3 3
1 0 0
0 1 0
0 0 1

예제 출력 2 

3

예제 입력 3 

4 3
1 2 3
6 5 4
7 8 9
12 11 10

예제 출력 3 

47

 

 

 

 

분석

NM사이즈의 미로에 각 방에는 사탕이 있다.

가장 왼쪽 위가 (1, 1), 가장 오른쪽 아래가 (n, m)

현재 (1, 1)에 있고 (n, m)으로 이동하려고 한다.

오른쪽과 아래쪽, 오른아래쪽 (3방향)으로 이동할 수 있고 각 방을 방문할 때 사탕을 모두 가져갈 수 있다.

준규가 (n, m)으로 이동할 때 가져올 수 있는 사탕의 최대값을 구하는 문제

 

풀이 과정

n = y값 세로 row , m = x값 가로 col

n번반복

  m번반복 사탕의 개수

 

완전탐색으로 풀 경우 시간초과가 날 것이다.
출발지에서 시작하는 것이 아니라 도착지에서 가장 큰 값을 더해가면서 출발지로 가면 최대값이 나온다.
다음 위치로 갈 수 있는 방향은 오른쪽과 아래쪽, 오른아래쪽 방향이다.
이걸 반대로 생각해서 왼쪽과, 위쪽 왼위쪽 3방향에 있는 사탕 중 가장 큰 사탕이 있는 곳으로 간다.

 

사탕의 개수를 입력받는다.

var map = [[Int]]()
map.append(Array(repeating: 0, count: m+1))

for _ in 0..<n {
    map.append([0] + readLine()!.split(separator: " ").map{ Int($0)!})
}

(1, 1)에서 시작하기에 x,y좌표 0인곳은 0으로 채워준다.

 

사탕의 합계를 저장해줄 배열을 선언해준다.

var candySumArr = Array(repeating: Array(repeating: -1, count: m+1), count: n+1)

 

0으로 채워진 곳은 어차피 갈 수 없는 곳이기 떄문에 합계도 0으로 채운다.

그리고 왼쪽과 위쪽의 최대값을 구해서 자신의 값과 더하고 배열에 저장한다.

대각선의 위치를 구하지 않는 이유는 어차피 최소거리를 구하는 것이 아니고 대각선으로 가는 것보다는 한번더 이동하는 것이 더 많은 사탕을 가질 수 있기 때문이다.

 

func dp(y: Int, x: Int) -> Int {
    if y == 0 || x == 0 {
        candySumArr[y][x] = 0
    }
    if candySumArr[y][x] < 0 {
        candySumArr[y][x] = map[y][x] + max(dp(y: y-1, x: x), dp(y: y, x: x-1))
    }
    return candySumArr[y][x]
}

 

 

풀이

let input = readLine()!.split(separator: " ").map{ Int($0)!}
let (n, m) = (input[0], input[1])

var map = [[Int]]()
map.append(Array(repeating: 0, count: m+1))

for _ in 0..<n {
    map.append([0] + readLine()!.split(separator: " ").map{ Int($0)!})
}

var candySumArr = Array(repeating: Array(repeating: -1, count: m+1), count: n+1)

func dp(y: Int, x: Int) -> Int {
    if y == 0 || x == 0 {
        candySumArr[y][x] = 0
    }
    if candySumArr[y][x] < 0 {
        candySumArr[y][x] = map[y][x] + max(dp(y: y-1, x: x), dp(y: y, x: x-1))
    }
    return candySumArr[y][x]
}

print(dp(y: n, x: m))

 

결과

 

 

 

---

📂  정리

문제를 처음시작으로 푸는 것이 아니라 마지막에서 거꾸로 생각하는 것이 새로운 문제였다.

 

그리고 배열의 사이즈를 정하는 것이 조금 헷갈렸다.

그림을 그리면서 하나씩 차근차근 하면서 풀었다.