방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용하면 쉽게 해결할 수 있는 문제였습니다. 이동할 수 있는 경우는 오른쪽, 아래 2가지 경우만 존재하므로 원본 배열과 같은 크기의 visited 배열을 만듭니다. 이후의 과정은 다음과 같습니다.

1. visited 배열을 조회함(0행 0열부터 n-1행 n-1열 까지)

2. 해당 칸이 직전 과정에서 이동한 칸이면(visited[i][j] != 0 이면) 위 또는 아래로 원본 배열에 해당하는 칸만큼 움직이기 단, 원본 배열의 해당 칸은 0이 아님

이 과정을 반복하면서 마지막에 도착했을 때 출력하면 됩니다.

소스코드

n = int(input())
dx = [0, 1]
dy = [1, 0]

graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
visited = [[0] * n for _ in range(n)]
visited[0][0] = 1

for i in range(n):
  for j in range(n):
    if graph[i][j] != 0 and visited[i] != 0:
      for k in range(2):
        nx = i + dx[k]*graph[i][j]
        ny = j + dy[k]*graph[i][j]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
          continue
        visited[nx][ny] += visited[i][j]
print(visited[n-1][n-1])