[백준]11048 이동하기 - 실버2

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• DP, 구현

---

1. 문제설명

 

N, M 크기의 미로를 탈출하는데 탈출할 때 미로에 놓여진 사탕을 최대한 많이 들고 탈출하려 합니다.

 

미로에서 이동하는 방법은 3가지 존재합니다.

0, 0 위치를 기준으로 0, 1 로 이동하기 / 1, 0 으로 이동하기 / 1, 1 로 이동하기

총 3가지가 존재할 때 가장 N, M 위치로 이동하여 탈출할 때 가장  많은 사탕을 들고 탈출 하는 방법을 구하는 문제입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 256 MB
• 1 ≤ N, M ≤ 1,000
• 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

---

2. 접근방식

이번 문제 역시 점화식만 잘 세우면 쉽게 해결 가능한 문제입니다.

 

문제에서 현재 위치를 기준으로 다음 위치로 이동할 때 이동 하는 방법은 3가지가 존재했습니다.

 

반대로 생각하면 이 위치로 올 수 있는 경우의 수가 3가지란 소리 입니다.

 

이 그림을 보면 좀더 이해가 쉬울 겁니다.

 

초록색으로 칠해진 1칸에 오기 위해서는 노란색 칸 3가지 경우중 가장 사탕이 많이 있는 칸에서 와야 합니다.

 

이를 이용해 DP의 누적 배열을 생성해보면 될 것 같습니다.

 

 

그럼 이 초록색 2칸에 오기 위해서는 노란색 3칸 중 한 칸에서 와야 하는데 사탕이 가장 많이 있는 칸은 1칸 이므로 

 

1 칸에서 초록색 2칸으로 이동하는게 가장 많은 사탕을 들고올 수 있는 경우 겠죠 이런 방식으로 DP의 점화식을 세워보면 다음과 같습니다.

 

 

현재 위치 DP[i][j] 는 이전 3가지 위치 중 한 군데 DP[i - 1][j] / DP[i][j - 1] / DP[i - 1][j - 1] 3군데 중 사탕이 가장 많은 칸에서 이동하고 현재 칸에 위치한 사탕의 개수와 합쳐 누적 배열을 생성해 주면 되겠죠

 

그러기 위해선 DP 배열을 indexError가 발생하지 않도록 생성 과 초기화를 해주어야 할 겁니다. 

 

코드로 문제를 해결해 보겠습니다.

---

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(N)]

# indexError 방지를 위해 왼쪽과 상단에 패딩값 추가한 배열 생성
DP = [[0] * (M + 1) for _ in range(N + 1)]

# DP 누적 배열을 위해 DP 기본 배열 초기화
# maze[0][0] 을 DP[1][1] 로 이동
for i in range(1, N+1):
    for j in range(1, M+1):
        DP[i][j] = maze[i - 1][j - 1]

# 점화식을 토대로 누적값 채우기
for i in range(1, N + 1):
    for j in range(1, M + 1):
        DP[i][j] = DP[i][j] + max(DP[i - 1][j], DP[i][j - 1], DP[i - 1][j - 1])

# 출력
print(DP[N][M])

 

먼저 입력을 받고 DP 배열을 생성해 주었습니다.

 

indexError를 방지하기 위해 왼쪽과 상단에 패딩값을 추가한 크기로 DP 배열을 생성해 주었고

 

입력받은 maze 배열을 돌며 maze의 [0][0] 위치를 DP[1][1]로 이동시켜 DP 배열을 누적배열로 만들기 위한 초기 설정을 실시해 주었습니다.

 

이 후 손코딩을 통해 찾은 패턴을 토대로 점화식을 세웠고 코드로 그대로 구현했습니다.

 

DP[i][j] 의 누적값은 DP[i][j] 값에 이전 3가지 위치 중 가장 큰 값을 더해 주면 되겠죠

 

max를 이용해 가장 큰 값을 선택 후 해당 값과 현재 위치의 값을 더해 누적배열을 생성해 주었습니다.

 

그 후 N, M 위치를 출력해 주었습니다.

---

4.결과

---

[회고]

이번 문제 역시 점화식을 잘 세워서 쉽게 해결이 가능한 문제 였습니다.

 

처음 점화식을 세울 때 누적값 적용을 위해 DP 배열을 초기화 하지 않고 바로 DP 와 maze를 각각 건드리려고 하니 생각보다 더 코드가 복잡해져서 간단히 DP 배열을 먼저 초기화 시킨 후 누적배열을 생성해 주었습니다.

 

또 처음에는 현재 위치에 오는 방법을 조금 다르게 생각해 점화식을 이상하게 세웠었습니다.

DP[i][j] = max(DP[i - 1][j - 1] + DP[i - 1][j], DP[i - 1][j - 1] + DP[i][j - 1])

 

처음에는 점화식을 이렇게 세웠는데 값이 중복이 되고 숫자가 많이 커지더라구요

 

특히

3 3

1 0 0

0 1 0

0 0 1 

 

예제를 실행 시켰는데 결과값으로 8이 나와서 수정했었습니다.

위 예제에서는 최대 3이 나와야 하는데 8이 나왔다는 것은 값을 2중으로 더해주었단 의미 이기 때문이죠

 

값이 누적된 부분을 생각해 보니 현재 위치에 도착하는 방법과 세웠던 점화식이 많이 다르다는걸 알았고 처음부터 손코딩을 토대로 점화식을 다시 세웠습니다.

 

그 결과 나온 점화식이 3가지 길 중 하나를 선택해 오는 방법 이었고 문제를 해결할 수 있었습니다.

 

다음 시간에도 DP 문제집을 풀며 DP 실력 향상을 목표로 노력하겠습니다.