[백준 1890 🥈] 점프

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

1890번: 점프

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2^63-1보다 작거나 같다.

 

문제 풀이

• 맨 상단 왼쪽부터 하단 오른쪽까지 이동하기 때문에, for문 탐색을 통해 [0][0] 위치에서 시작해서 [n-1][n-1]에 도달해서 점프가 종료될 때까지 탐색한다.
• 여기서, DP를 사용해서 각 위치까지 올 수 있는 경우의 수를 저장해줬다.
  • dp[i][j] : 시작점에서 출발해서 [i][j]까지 올 수 있는 경우의 수
• for문 탐색을 통해서 현재 위치가 dp 값이 아니라면 해당 위치에 가는 경로가 존재하는 것이므로, 아래도 step[i][j] 만큼 가는 경우나 오른쪽으로 step[i][j]까지 가는 경우가 범위 안의 값이라면 이동한 위치에 현재 위치의 dp 값을 추가해서 이동한 위치에 도달할 수 있는 경우의 수를 갱신한다.
• 이러한 과정을 거쳐서 마지막에 도달하면 for문을 종료하고 나오게 되는데, 여기서 주의할 점은 step[i][j]가 0인 경우엔 현재 y 위치+0, 현재 x 위치 +0으로 범위 안에 해당하는 것으로 판단해서 step[i][j](즉, 종점)에서 자기 자신을 더 해주지 않도록 step[i][j]가 0이 아닌 경우에만 연산을 수행하도록 조건을 걸어줘야 올바른 값을 출력할 수 있다.

import sys

n=int(sys.stdin.readline())
step=[list(map(int, sys.stdin.readline().split(' '))) for _ in range(n)]
# 각 위치까지 올 수 있는 경우의 수
dp=[[0]*(n) for _ in range(n)]
dp[0][0]=1
for i in range(n):
    for j in range(n):
        # 0이 아닌 경우, 즉 방문 가능한 칸인 경우
        # step이 0인 경우엔 i+step[i][j], j+step[i][j] 모두 그 자리 그대로인 것으로 계산되어서 현재 위치의 dp값을 더해주기 때문에 계산해선 안된다
        if dp[i][j]!=0 and step[i][j]!=0:
            # 현재 칸에 해당하는 점수만큼 점프해서 dp 값 갱신
            if i+step[i][j]<n:
                dp[i+step[i][j]][j]+=dp[i][j]
            if j+step[i][j]<n:
                dp[i][j+step[i][j]]+=dp[i][j]

print(dp[n-1][n-1])

https://www.acmicpc.net/board/view/119014

글 읽기 - BFS로 해당 문제를 풀 수 없는 이유 (주관적인 생각)

<이 문제를 BFS로 풀 수 없는 이유>