[프로그래머스 동적계획법/DP]등굣길 - Python3

문제

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

코딩테스트 연습 - 등굣길 | 프로그래머스

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

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력

m	n	puddles	return
4	3	[[2,2]]	4

알고리즘

k

 

설명

문제를 풀기 위해, 다음과 같이 2차원 배열을 만들 것이다. 

	집
				학교

위 표를 보면 왼쪽과 위쪽에 열과 행이 아나씩 추가된 것을 볼 수 있다. 이는 인덱스를 통해 배열에 접근함에 있어서, 인덱스를 맞춰주어서 편하게 풀기 위함이다. 

0	0	0	0	0
0	1(집)	아직 값 없음	아직 값 없음	아직 값 없음
0	아직 값 없음	아직 값 없음	아직 값 없음	아직 값 없음
0	아직 값 없음	아직 값 없음	아직 값 없음	학교

이렇게 초기값을 주고, 집이 있는 (1,1) 부터 학교가 있는 (n, m)까지 반복하면서 각 칸에 값을 채우고, 마지막 칸인 board[n][m]을 리턴할 것이다. 색칠한 부분이 우리가 2중 for문으로 반복할 부분이다.

이 문제를 풀기에 앞서, DP 예제 3번인 동전 줍는 로봇 문제를 떠올려 보면, 이 문제와 아~~~주 많은 부분이 같다는 것을 알 수 있다. 문제가 뭐였는지 기억이 안난다면 아래 링크를 참조하시라~

2020/01/30 - [공부/알고리즘] - [알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

[알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

또한, 우리는 초등학교 또는 중학교때 경우의 수를 배우면서, A지점에서 B로 가는 경우의 수를 쉽게 구하는 법을 배웠다. 예를 들면,

A
			B

A에서 B로 가는 경우를 구하려면, 각 칸에 어떤 값을 하나씩 써가면서, B지점에 마지막으로 쓰여지는 값이 정답이었다. 즉, 

A	1
1
			B

A에서 오른쪽, 아래쪽으로 한번 움직일 때마다, 그 칸에 1을 써넣는다. 

A	1
1	2
			B

그리고, 위의 경우처럼, 어떤 지점으로 가려고 할 때 위쪽에서 내려올 수도 있고, 왼쪽으로 오른쪽으로 올 때도 있는 경우, 왼쪽의 값과 위쪽의 값을 더한 값을 해당 칸에 쓴다. 

A	1	1	1
1	2	3
1			B

이런 식으로 쭉 가다보면, B 지점은 다음과 같이 구해진다

A	1	1	1
1	2	3	4
1	3	5	9

 

이미 배운 방법이고, 예제3: 동전 줍는 로봇으로 실습도 해봤으니 문제를 간단하게 풀 수 있다. 다만 다른점은, 갈수 없는 지점(puddles) 가 있다는 것이다. puddles의 각 원소는 웅덩이가 있는 곳의 x좌표와 y좌표를 가지고 있다. 따라서, i,j 2개의 인덱스를 사용해서 해당 칸에 값을 써 넣을 것인데, 만약 board[j][i]가 puddles에 있는 원소라면, 그 칸의 값은 다음 계산에 영향을 미치지 못하도록 0을 쓸 것이다. 

def solution2(m, n, puddles):
    board = [[0]*(m+1) for i in range(n+1)]
    board[1][1] = 1
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 맨 첫칸
            if i == 1 and j == 1:
                continue
            
            # 해당 칸이 웅덩이인 경우
            if [j, i] in puddles:
                board[i][j] = 0
                
            # 해당 칸의 바로 위 칸의 값과, 왼쪽 칸의 값을 더한 결과를 써넣는다.
            else:
                board[i][j] = board[i-1][j] + board[i][j-1]
    answer = board[n][m]
    return answer % 1000000007

코드로 구현하면 다음과 같다. 

위에서 말했던 예시와 코드를 좀 더 구체적으로 설명하자면, 다음과 같다

1. board[1][1]은 출발지이므로, 반복문에서 별다른 조치를 하지 않고 continue한다.
2. [j, i]가 puddles의 원소라면, 그 칸은 웅덩이라는 뜻으로, 갈 수 없는 칸이다. 따라서 값을 0으로 한다
3. 그렇지 않다면, 바로 위쪽 칸의 값과 왼쪽 칸의 값을 더한 값을 결과로 써 넣는다

2에 의해서 갈수 없는 칸의 값을 0으로 했기 때문에, 다음 칸의 값을 정하는데 영향을 주지 못한다(0을 더하기 때문). 

결과

원하는 결과를 출력한다

후기

말했다시피, 예제 3번의 문제에 응용 한 꼬집을 더한 문제였다. DP공부자료는 모두 알고리즘 과목때 강의노트를 다시 한 번 보면서 정리한 건데, 문제를 풀 때 여러 모로 도움이 된다. 정말 감사합니다~