백준 1520번 문제(내리막길) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

1520번: 내리막 길

 

정답 코드는 아래와 같습니다.

import sys
 
direction = [(0, -1), (0, 1), (-1, 0), (1, 0)]
 
def calc(rst, table, m, n, p, q):
  if p == m - 1 and q == n - 1:
    rst[p][q] = 1
    return
  if rst[p][q] != -1:
    return
  rst[p][q] = 0
  for dp, dq in direction:
    np = p + dp
    nq = q + dq
    if 0 <= np < m and 0 <= nq < n:
      if table[p][q] > table[np][nq]:
        calc(rst, table, m, n, np, nq)
        rst[p][q] += rst[np][nq]
 
def solve():
  m, n = map(int, sys.stdin.readline().rstrip().split())
  table = []
  for _ in range(m):
    arr = list(map(int, sys.stdin.readline().rstrip().split()))
    table.append(arr)
  rst = [[-1] * n for _ in range(m)]
  calc(rst, table, m, n, 0, 0)
  print(rst[0][0])
 
solve()

 

이 문제는 가장 어려운 유형 중 하나인, DP + alpha 문제입니다. 여기서는 alpha 가 DFS 인 경우입니다.

2021년도 카카오 신입 공채 1차 온라인 코딩테스트 7번 문제와 유사합니다.

상당히 어려운 문제이기 때문에 보통 기업 코딩테스트에서 잘 나오지 않는 유형이었으나, 요즘 이렇게 출제되는 것을 보면 상향 평준화가 되었다는 생각이 듭니다.

 

728x90

 

제 다른 영상을 보신 분들은 아시겠지만, 제 풀이는 이미 답을 아는 사람이 그 답을 설명해주는 것이 아니라, 저도 답을 모르고 처음 보는 상황이라고 가정하고, 어떻게 풀이를 찾아나가는지를 보여주고 있습니다.

생각의 흐름이 저와 동일할 필요는 없습니다만, 제가 결국 풀이를 어떻게 찾아내는지를 유심히 관찰해보시면, 공부하시는데 도움이 되리라 생각합니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=x4XpprJMMIY 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)