본문 바로가기

Problem Solving/programmers

[Programmers] 등굣길(Python) / Dynamic Programming

 

코딩테스트 연습 - 등굣길

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =

programmers.co.kr

 

  • 사용 알고리즘 : Dynamic Programming(동적 계획법)
  • 맵의 크기보다 행 + 1, 열 + 1 크기만큼 크게 만든다.
  • 시작 위치(1, 1)는 넘어가고, 물 웅덩이(-1) 표시된 부분은 0으로 바꿔줌.
  • 이외의 위치별로 좌, 상 방향의 숫자들을 더하며 끝까지 채운다.
  • 가장 오른쪽 하단의 값(A[n][m])을 주어진 값(100,000,000,007)으로 나눈 나머지를 리턴한다.

 

파이썬 코드는 다음과 같다.


def solution(m, n, puddles):
    A = [[0] * (m+1) for _ in range(n+1)]
    A[1][1] = 1				# 시작 위치 표시
    
    for pr, pc in puddles:	# 물 웅덩이 표시
        A[pc][pr] = -1

    for r in range(1, n+1):
        for c in range(1, m+1):
            if (r, c) == (1, 1):	# 시작 위치는 무시
                continue
            if A[r][c] == -1:		# 물 웅덩이면 0으로 바꿔줌
                A[r][c] = 0
            else:
                A[r][c] += (A[r-1][c] + A[r][c-1])	# 좌, 상 방향의 값을 더해줌
        
    return A[n][m] % 1000000007

  • 고찰 : 어렵지 않은 DP 문제였다! 더 더 많이 풀고 익숙해지자.