백준 1890 파이썬 문제 풀이

백준 1890번 문제

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

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

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

입력

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

출력

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

 

 

 

문제접근 방법

1. BFS 접근

- 이 문제는 BFS로 접근할 경우 큰 문제가 있다. 메모리 초과가 발생한다는 점이다. BFS는 일반적으로 QUE로 구현을 하게 되는데, 내가 짠 코드는 방문했던 곳을 끊임없이 업데이트를 해야한다는 점이다. 이 경우, 방문한 곳을 끊임없이 QUE에 넣어야 하기 때문에, n의 수가 커지면 커질수록 QUE에 들어가는 값이 어마어마하게 많아진다.

즉, Visited List를 사용하지 않으면 메모리 초과 및 시간 초과가 필수적으로 따라온다. 그래서 Visited List를 사용해서 구현을 해보려 했으나, 나 같은 경우에는 아이디어가 떠오르지 않아서 BFS로 접근하는 것을 포기했다.

2. 이중 For문으로 접근

- 다이나믹 프로그래밍에 가장 가까운 방법이 아닐까 싶다. 윗쪽부터 하나씩 칸을 체크하면서 접근하는 방법이다. 예를 들어 [1,1]~[1,4]까지 체크하고, [2,1] ~ [2,4] .... [4,1] ~ [4,4]까지 체크하는 방식으로 진행한다. 이 방식에서 [1,1]에 접근했을 때, 들어있는 값을 확인한다. 들어있는 값으로 다음 좌표를 확인한 후, 다음 좌표가 존재한다면 현재 위치의 접근 방법을 업데이트 하는 방법이다.

예를 들어서 [2,2]로 접근하는 방법이 이미 3가지가 있다고 가정을 해보자. 그런데 [2,1]을 아직 점검하지 않은 상황이었는데, [2,1]에 접근하는 가지수를 2가지이고, [2,1]에 들어있는 점프 수가 1이라고 가정을 해보자. 그럼 [2,1]에서 다음으로 갈 수 있는 위치는 [2,2]와 [3,1]인데, 이 때 [2,2]와 [3,1]에 가는 가지수를 업데이트 한다. 이렇게 되면 [2,2]에 접근하는 방법은 기존 2가지 방법에 [2,2]로 접근하는 2가지 방법을 더한 값인 4가지가 된다.

즉, 이를 처음부터 끝까지 반복하게 되면 마지막 위치로 가는 방법의 값이 확인된다. 단, 이 경우 n,n이 됐을 때는 체크를 하지 않고 끝내도록 해야한다. 그럴 경우 중복이 되기 때문이다.

import sys
n = int(sys.stdin.readline().rstrip())
my_map = [ [0] for _ in range(n+1)]
for z in range(1,n+1):
    temp = list(map(int, sys.stdin.readline().split()))
    for k in temp :
        my_map[z].append(k)

d = [[0 for _ in range(n+1)] for _ in range(n+1)]
d[1][1] = 1

for i in range(1,n+1) :
    for j in range(1,n+1) :
        if i == n and j == n :
            break
        r = i
        c = j
        next_r = r + my_map[r][c]
        next_c = c + my_map[r][c]
        if 0 < next_r < n+1 :
            d[next_r][c] += d[r][c]
        if 0 < next_c < n+1 :
            d[r][next_c] += d[r][c]


print(d[n][n])