[백준/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)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

 

---

문제는 다음과 같이 풀었다.

 

• 각 위치마다 캔디의 개수가 들어 있는 candy_map과 크기가 동일하고 모든 요소가 0인 dp_map 2차원 리스트를
  만든다.
• 리스트의 모든 요소를 탐색하면서 dp_map의 현재 위치(x, y)에 dp_map [x-1][y]와 dp_map [y][x-1] 중
  큰 값을 넣어준다.
  
  
• 마지막으로 현재 위치와 동일한 위치의 candy_map에 있는 캔디의 개수를 추가해 준다.

 

이동 경로는 우측으로 한 칸, 아래로 한칸, 대각선으로 한칸 총 3가지 방식이 있지만 대각선으로 가는 경우는

생각하지 않는다. 왜냐하면 대각선으로 가는 경우는 우측으로 내려갔다 아래로 내려가거나, 아래로 내려갔다가 우측으로 내려가는 경우보다 절대 최댓값을 가질 수 없기 때문이다.

글로만 보면 이해하기 어려울 수 도 있으니 그림을 그려보자.

 

---

 

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

candy_map

먼저 각 위치에 캔디의 개수를 넣어 준 2차원 리스트 하나와

 

0	0	0	0
0	0	0	0
0	0	0	0

dp_map

크기는 동일하고 모든 요소가 0인 2차원 리스트 하나를 더 만들어 준다.

우리는 여기에다가 값을 넣어줄 것이고, 최종적인 출력 값도 이 리스트 요소 값을 출력할 것이다.

 

1	0	0	0
0	0	0	0
0	0	0	0

 

가장 처음의 인덱스인 dp_map [0][0] 에는 현재 위치의 캔디 개수만 들어간다.

 

1	1 + 2 = 3	0	0
0	0	0	0
0	0	0	0

 

그다음 위치에는 dp_map [x-1][y]와 dp_map [x][y-1] 값을 비교하는데 dp_map [x-1][y]의 값 밖에 없으므로

이에 해당하는 dp_map [0][0]과 candy_map [1][1]를 더한 값을 넣어준다.

 

1	3	6	10
1	3	9	15
10	0	0	0

 

좀 더 진행되었을 경우를 보자. 현재 dp_map [2][1]의 위치에 값을 넣을 차례다. 먼저 dp_map [2-1][1]과 dp_map [2][0]의 값 중 최댓값을 넣어준다.

 

1	3	6	10
1	3	9	15
10	10	0	0

 

dp_map [2-1][1]과 dp_map [2][0]의 값 중 최댓값인 10을 넣는다.

 

그다음 해당 위치와 동일한 위치의 candy_map 요소를 추가로 더해준다.

 

1	3	6	10
1	3	9	15
10	10+8 = 18	0	0

 

최종적으로 나오는 dp_map은 다음과 같다.

 

1	3	6	10
1	3	9	15
10	18	25	31

 

모든 탐색을 완료하고 가장 마지막 요소 값을 출력하면 끝!

 

코드는 다음과 같다

a,b = map(int,input().split()) # 행렬 크기 지정
candy_map = [[int(n) for n in input().split()] for _ in range(a)] # 캔디맵 생성
dp_map = [[0 for _ in range(b)] for _ in range(a)] # 각 인덱스에 최댓값을 넣어놓는 곳

for x in range(a) :
    for y in range(b):
        dp_map[x][y] = max(dp_map[x-1][y],dp_map[x][y-1]) #이전에 있던 좌표 값에서 큰 값을 가져옴
        dp_map[x][y] += candy_map[x][y] # 현재 위치와 동일한 위치의 캔디값을 더해준다.

print(dp_map[a-1][b-1])

다이내믹 프로그래밍을 이용해서 풀어보는 문제를 많이 경험해 보질 못 해서 생각하는데 어려움이 많았지만,

끈질기게 물고 늘어지다 보면 풀리긴 하는 걸 보니 신기방기 하다.