[백준/1890] 점프 (Python)

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

1890번: 점프

 

Difficulty : Silver 1

 

Status : Solved

 

Time : 00:05:17

 

---

 

문제 설명

 

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

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

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

 

입력 및 출력

 

입력

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

 

출력

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

입력 예시

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

 

출력 예시

 

3

 

 

---

 

풀이

 

DP 문제. 어떤 특정한 좌표의 노드에서 종착지까지 가는 경우의 수는 항상 동일하므로, 이를 이전에 탐색한 적 있다면 그 경우의 수를 바로 반환한다는 관점으로 생각하면 편하다.

 

이를테면, (1, 1)에서 (3, 3)좌표(도착점)로 가는 경우의 수가 5가지가 있다고 가정하자. (0, 0)좌표(출발점)에서 (0,0) -> (0,1) -> (1,1), (0,0) -> (1, 0) -> (1, 1)로 가는 두 가지 경로 모두, 결국 (1, 1)로부터 (3, 3)으로 가는 도착점의 경우의 수를 공유한다. 따라서 위 두 경로의 총 경우의 수는 5*2 = 10가지가 된다.

 

풀이 코드

import sys
input = sys.stdin.readline

dx = [1, 0]
dy = [0, 1]

N = int(input())
map_list = [list(map(int, input().split())) for _ in range(N)]

dp = [[-1]*N for _ in range(N)]
dp[-1][-1] = 1

def dfs(x, y) :
  if dp[y][x] > -1 :
    return dp[y][x]
  if map_list[y][x] == 0 :
    return 0
  dp[y][x] = 0
  for k in range(2) :
    ax, ay = x + map_list[y][x]*dx[k], y + map_list[y][x]*dy[k]
    if -1 < ax < N and -1 < ay < N :
      dp[y][x] += dfs(ax, ay)
  return dp[y][x]

print(dfs(0, 0))

풀이 완료~