[백준]1890 점프 - 실버1

[오늘의 문제]

 

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

---

[오늘의 학습 키워드]

• DP, 구현

---

1. 문제설명

 

N x N 크기의 미로에서 0, 0 위치에서 시작해 N, N 위치로 이동하는 경로의 수를 구하는 문제 입니다.

 

이동은 반드시 오른쪽 혹은 아래쪽으로만 가능하며 현재 도착한 칸에 이동 가능한 칸의 개수가 적혀 있습니다.

 

예를들어

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

 

이렇게 미로가 주어진 경우 0, 0 위치에서 다음 이동 가능한 위치는 2칸 이동해서 0, 2 혹은 2, 0 이겠죠

 

이런식으로 N, N 위치까지 이동할 때 발생가능한 경로의 수를 모두 구하는 문제 입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 128MB
• 4 ≤ N ≤ 100
• 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.
• 경로의 개수는 263-1보다 작거나 같다.

---

 

2. 접근방식

이번 문제는 구현의 느낌이 더 강한 DP 문제 였습니다.

 

0, 0 에서 시작해 다음 이동 가능 위치를 고려해 이동할 때 현재 위치에 있던 경로의 수를 다음 이동 위치에 더해주는 방식으로 누적 배열을 구해주면 될 것 같습니다.

 

 

board 판이 이렇게 주어질 때 0, 0 이 시작위치니 DP 배열의 0, 0을 1로 초기화 하고 점화식을 토대로 채워 나가면 될 것 같습니다.

 

이번 문제의 핵심은 다음 이동 위치가 board에 적힌 점프만큼 이동해야 한다는 것입니다.

 

0, 0 에서 2칸씩 점프해 오른쪽과 아래쪽으로 이동하는데 이때 0, 0 이 가진 경로의 수를 다음 이동 위치에 누적해서 구해주면 되겠죠

 

그럼 다음과 같이 생성 됩니다.

 

 

다음 이동 위치로 이동 했고 여기서 경로의 수는 기존 경로의 수 0개에 0, 0 위치에 존재하던 경로의 수 1개를 더해 각각 1개가 되었습니다.

 

여기서 다음 이동을 실시해 보죠 

 

다음 이동을 실시하면 이런식으로 구성될 것입니다.

 

마찬가지로 경로의 수는 1개씩 늘어나겠죠

 

또 3의 경우 미로를 벗어나기 때문에 오른쪽으로는 이동이 불가능 하고 아래쪽으로만 이동이 가능하죠

 

이런식으로 누적 이동을 완료하였을 때 최종적으로 N, N 의 위치에 생성될 경로의 수는 3개가 되어야 합니다.

 

이걸 점화식으로 세워보면 다음과 같습니다.

 

2차원 DP 배열을 생성하고 초기 위치를 설정하였다면 2중 for문을 통해 전체 탐색을 실시합니다.

 

이때 현재 위치에서 경로의 수를 들고 이동할 다음 이동 위치는 board[i][j] 에 적힌 수만큼 이동해야 하니

 

nx 와 ny를 각각 구해 다음 이동위치를 찾아주고 그 위치가 미로를 벗어나지 않는 경우 이동하는데, 해당 칸에 적힌 경로의 수에 들고온 경로의 수를 같이 더해주어야 겠죠

 

마지막으로 N, N 위치에 도착하면 더이상 탐색을 실시하지 않고 종료해 주면 될 것 같습니다.

 

코드로 구현해 보았습니다.

---

3. 코드

import sys
input = sys.stdin.readline

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

# DP 배열 생성 및 초기화
DP = [[0] * N for _ in range(N)]
DP[0][0] = 1    # 시작지점에 오는 경우의 수는 무조건 1 이상

# 점화식 토대로 다음 값 채우기
for i in range(N):
    for j in range(N):

        # N, N 위치인 경우 값을 더해주지 않기
        if (i, j) == (N - 1, N - 1):
            continue

        # 다음 위치는 현재 위치의 경로 수
        if DP[i][j] > 0:
            # 오른쪽 이동
            ny = j + board[i][j]
            if 0 <= ny < N:
                DP[i][ny] = DP[i][j] + DP[i][ny]
                
            # 아래로 이동
            nx = i + board[i][j]
            if 0 <= nx < N:
                DP[nx][j] = DP[i][j] + DP[nx][j]

print(DP[N-1][N-1])

 

입력을 받고 DP 배열을 생성한 뒤 0, 0 위치에 1값을 넣어 주었습니다.

 

시작위치 0, 0 에는 최소한의 경로 1개가 존재할 것이기 때문에 1로 초기화 해주었습니다.

 

이제 2중 for문을 통해 전체 탐색을 실시하는데 경로의 수가 존재하는 경우 다음 누적 경로를 찾아주면 되기 때문에

 

DP[i][j] 가 0 이상인 경우만 탐색을 실시해 주었습니다.

 

오른쪽 이동과 아래쪽 이동을 각각 구현해 주었는데

오른쪽 이동의 경우 i값은 그대로인데 j 값이 변화하는 것이기 때문에 ny로 설정하고 미로를 벗어나지 않아야 하기 때문에

0 <= ny < N 조건을 설정해 주었습니다.

 

이 조건에 만족한다면 다음 이동 위치에 경로의 수를 누적해 주었습니다.

 

동일하게 아래쪽 이동도 구현해 주었습니다.

 

마지막으로 i, j 가 N-1,N-1 에 도착한 경우 즉 마지막 위치에 도착한 경우 continue로 코드를 건너뛰고 출력해 주었습니다.

---

4.결과

---

[회고]

이번 문제는 점화식을 이용한 DP 문제보다는 구현 문제의 느낌이 강했습니다.

 

구현을 하며 다음 이동 위치와 누적 경로를 계산해 주는데 처음에는 제대로 이동을 구현해 경로가 DP 배열에 모두 찍혔는데 결과가 자꾸 틀리게 나와서 의아했습니다.

 

파이썬튜터를 통해 코드 동작과정을 살펴보니 마지막 N-1, N-1을 탐색할 때, 이 위치는 항상 경로의 수가 누적되어 0이상이라 오른쪽 이동과 아래쪽 이동에 걸리는 것이었습니다.

 

왜냐하면 board[N-1][N-1]은 항상 0이 주어지기 때문에 다음 이동위치가 자기자신 이었기 때문이죠

 

이것때문에 경로의 수가 누적이 되어 원래의 결과 x2, x2 가 발생하였습니다.

 

이를 해결하기 위해서 마지막 위치가 온 경우 break 혹은 출력후 종료 등을 생각했는데

 

크게 시간차이가 나진 않아서 간단히 continue로 건너뛰고 결과를 출력하여 문제를 해결할 수 있었습니다.

 

다음시간에도 DP 문제를 풀어보며 실력을 키워보겠습니다.