등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

I. 문제 개요

DP를 활용하여, 유효한 경로의 갯수를 찾아내는 문제이다.

 

II. 알고리즘 설계

0	0	0	0	0
0	1	0	0	0
0	0	0	0	0
0	0	0	0	0

 

0 : 패딩

0 : 웅덩이

 

dp 탐색에 사용할 2D-list는 위와 같이 초기화 할 수 있다.

 

윗쪽과 왼쪽에 0으로된 padding을 추가함으로써, 탐색할 때 경계를 넘어갈 경우에도 에러를 예방할 수 있다.

 

각 칸에 도달하는 경우의 수는 (현재 칸의 윗칸에 도달하는 경우의 수) 와, (현재 칸의 왼쪽 칸에 도달하는 경우의 수)의 합으로 구할 수 있다.

 

이 점화식을 이용하면, 주어진 예제를 아래의 표와 같이 풀 수 있다.

 

0	0	0	0	0
0	1	1	1	1
0	1	0	1	2( = 1 + 1)
0	1	1	2( = 1 + 1)	4(= 2 + 2)

 

 

III. 풀이

1. 변수 초기화 

MOD = 1000000007
dp = [[0] * (m+1) for _ in range(n+1)]   # 0으로 padding 추가 -> 경계 벗어날 우려 예방, puddles의 좌표 그대로 사용가능
dp[1][1] = 1   # dp 탐색 시작 위치

 

나머지를 구할 때 사용할 숫자를 저장하고, DP에 사용할 2D-list를 생성한다.

 

2D-list를 생성할 때 주어진 크기(n × m) 보다 1행, 1열 더 큰 크기 (n+1) × (m+1)로 생성해준다.

 

그 다음에는, 탐색을 시작할 위치 (1, 1)의 값을 1로 초기화한다.

 

 

2. DP

for i in range(1, n+1):         # 행 방향
    for j in range(1, m+1):     # 열 방향
        if ([j, i] in puddles) or (i == 1 and j == 1):  # 웅덩이거나, 시작위치라면 -> 무시
            continue
        else:
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD  # 경우의 수 계산

ans = dp[-1][-1]
return ans

 

현재 보고있는 칸이 출발지점 또는 웅덩이라면, 무시하고 다른 칸을 탐색한다.

 

그 외에는 왼쪽 칸에 도달하는 경우의 수(dp[i][j-1]), 윗쪽 칸에 도달하는 경우의 수(dp[i-1][j]) 끼리 더한 다음 MOD로 나눈 나머지 값을 구하고, 이를 dp[i][j]에 적어넣는다.

 

문제의 답은 dp의 마지막 줄, 맨 오른쪽 칸에 들어있는 값이다.

 

 

IV. 전체 코드

def solution(m, n, puddles):
	# 1. 변수 초기화
    MOD = 1000000007
    dp = [[0] * (m+1) for _ in range(n+1)]   # 0으로 padding 추가 -> 경계 벗어날 우려 예방, puddles의 좌표 그대로 사용가능
    dp[1][1] = 1   # dp 탐색 시작 위치
    
    # 2. DP    
    for i in range(1, n+1):         # 행 방향
        for j in range(1, m+1):     # 열 방향
            if ([j, i] in puddles) or (i == 1 and j == 1):  # 웅덩이거나, 시작위치라면 -> 무시
                continue
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD  # 경우의 수 계산
    
    ans = dp[-1][-1]
    return ans

 

 

V. 결과