[백준 1890번] 점프(파이썬)

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

1890번: 점프

이 문제는 DFS로 푸는 아주 간단한 문제입니다.

 

#점프

N=int(input())

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

x=0
y=0
count=0



def dfs(x,y):
  global count
  if graph[x][y]==0:
    count+=1
    #print(count)
    return
  now=graph[x][y]
  if y+now<N:
    dfs(x,y+now)
  if x+now<N:
    dfs(x+now,y)
  return

dfs(0,0)
print(count)

 

이렇게 길을 찾을 땐 DFS를 사용해서

간단하게 문제를 풀 수 있습니다.

 

 

라는 설명을 듣고

열심히 공부했는데

이 코드를 만약 그대로 입력한다면

시간초과를 맞이하게 됩니다.

분명 이거 길찾기 문제고

알고리즘 맞게 했는데 왜지??

하고 고민하다가

문제에서

'경로수는 2^63-1보다 작다'

라는 문구를 봤습니다.

저 숫자가 얼마인지는 정확히는 몰라도

여튼 DFS로 재귀함수로 계속 풀다보면

파이썬의 재귀제한으로 나가버리겠구나

생각이 들었습니다.

그래서 DP로 푸는 방식을 택했습니다.

여기서는 중딩때부터 줄곧 풀던

'최소의 경로수'를 구하는

풀이를 활용했습니다.

어릴 때 a에서 b까지의 경로를 구할 때

저렇게 경로를 더해줘서 구했던 경험이 있습니다.

이를 코딩으로 옮겨주면서

이 문제를 해결할 수 있었습니다.

 

#점프

N=int(input())

graph=[list(map(int,input().split())) for _ in range(N)]
dp=[[0]*N for _ in range(N)]
x=0
y=0
now=graph[x][y]

#0 0을 기준으로 경로초기화
if x+now<N:
  dp[x+now][y]=1
if y+now<N:
  dp[x][y+now]=1

for i in range(N):
  for j in range(N):
    if dp[i][j]: #dp에 값이 있다는 말은, 0 0에서부터 쭉 점프에서 왔다는 말.
      now=graph[i][j]
      count=dp[i][j]
      if now==0:
        continue
      if i+now<N:
        dp[i+now][j]+=count #범위안에 들면, 현재 경로수를 점프한 곳에 더해준다.
      if j+now<N:
        dp[i][j+now]+=count
#print(dp)
print(dp[N-1][N-1])

 

이 문제를 풀면서

'길찾기는 무조건

DFS BFS야.'

라고 무지성으로 접근하는 것에 대한

반성도 하게 되었습니다.

물론 대부분의 길찾기 문제는

저 2개를 쓰면 풀리는 게 대부분이지만

이렇게 경로의 수가 많아져버린다면

시간초과가 일어나게 됩니다.

만약에 내가 구현한 코드가

논리적으로 맞은 거 같은데

시간초과가 뜬다면

DP로 접근할 수 있음을 배웠습니다.