프로그래머스 - 등굣길
https://programmers.co.kr/learn/courses/30/lessons/42898
문제 설명
폭우로 인해 일부 지역이 물에 잠겼다.
물에 잠기지 않은 지역을 통해 최단거리로 학교를 가는 방법이
몇 가지가 있는지 알아보자.
경우의 수가 커질 수 있으니, 1,000,000,007로 나눈 나머지를 리턴하자.
제한 사항
- 1 <= 가로, 세로 길이 <= 100
- 가로와 세로 길이가 모두 1인 경우는 주어지지 않는다.
- 0 <= 물에 잠긴 지역 <= 10
- 집이나 학교가 물에 잠긴 경우는 없다.
1. DP - O(N^2)
맨 왼쪽 위에서부터 맨 오른쪽 아래까지를 최단거리로 가는 경우의 수를 묻는 문제다.
그리고 경우의 수가 굉장히 많이 나올거라며 미리 경고를 하기도 한다.
그러면 최단거리로 가기 위해선 어떻게 해야 할 까?
간단하다. 왼쪽이나 위로는 절대 가지 않고, 오른쪽이나 아래로만 가면 된다. 왼쪽으로 간다는 것은, 이 후로 오른쪽으로 두 번 더 가야 한다는 것을 의미하며, 위로 간다는 것은, 이 후로 아래로 두 번 더 가야 한다는 것을 의미한다.
위의 사항이 문제의 의도인 것 같다. 위의 이미지처럼, 웅덩이의 위치에 따라 위나 아래로 이동해야 학교에 도달하는 경우도 있을 수 있다. 하지만 이 문제에서는 이런 이동은 최단 경로로 보지 않는 것으로 보인다.
그러면 2 x 3 크기의 지역에서, 집에서 학교까지 최단거리로 가는 방법은 몇 가지일까?
오른쪽 - 아래 - 아래
아래 - 오른쪽 - 아래
아래 - 아래 - 오른쪽
총 3가지 방법이 있다.
그러면 3 x 4 크기의 지역에서, 학교까지 최단거리로 가는 방법은 몇 가지일까?
오른쪽 - 오른쪽 - 아래 - 아래 - 아래
오른쪽 - 아래 - 오른쪽 - 아래 - 아래
오른쪽 - 아래 - 아래 - 오른쪽 - 아래
오른쪽 - 아래 - 아래 - 아래 - 오른쪽
아래 - 오른쪽 - 오른쪽 - 아래 - 아래
아래 - 오른쪽 - 아래 - 오른쪽 - 아래
아래 - 오른쪽 - 아래 - 아래 - 오른쪽
아래 - 아래 - 오른쪽 - 오른쪽 - 아래
아래 - 아래 - 오른쪽 - 아래 - 오른쪽
아래 - 아래 - 아래 - 오른쪽 - 오른쪽
총 10가지 방법이 있다.
자세히 보면 m-1개의 아래와 n-1개의 오른쪽을 배열하는 가짓수가
곧 최단거리로 이동하는 경우의 수라는 것을 확인할 수 있다. 이를 식으로 표현하면
(m+n-2)! / (m-1)!(n-1)!
로 표현할 수 있다. 만약에 m과 n이 각각 100이라면? 어마어마한 경우의 수가
나올 것이다. 괜히 총 경우의 수의 나머지를 구하는 것이 아니다.
하지만 안타깝게도 위의 경우의 수는 쓸 일이 없다. 웅덩이의 존재가 있기 때문이다. 위의 경우의 수를 돌려보면서 실제로 웅덩이를 만나는 경우의 수를 제외한다? 검사해야 할 경우의 수가 너무 많다. m = 100, n = 100일 경우, 가능한 경우의 수는
22750883079422934966181954039568885395604168260154104734000
가지가 된다. 이 경우의 수를 모두 찾아가며 웅덩이에 빠지는 경우의 수를 빼는 방법으로는 어림도 없다. 무언가 다른 방법을 찾아야 한다.
좌표 (5,5)가 있다. 이 (5,5)는 어떻게 해야 도달할 수 있을까?
(4,5) 또는 (5,4)에서 아래/오른쪽으로 이동하면 도달할 수 있는 곳이다.
그러면 (5,5)로 갈 수 있는 경우의 수는 몇 가지라고 할 수 있을까?
(4,5)로 갈 수 있는 경우의 수와 (5,4)로 갈 수 있는 경우의 수를 더하면,
(5,5)로 갈 수 있는 경우의 수라고 할 수 있을 것이다.
(4,4)에서 바로 (5,5)로 갈 수는 없고, (6,5)나 (5,6)에서
왼쪽/위쪽으로 올 수는 없기 때문이다.. (5,5) 직전에 올 수 있는 좌표는
(4,5)와 (5,4) 뿐이다.
(i+1,j+1)에 도달할 수 있는 경우의 수를 저장한 배열 d가 있다고 치자.
그러면 d[i][j]는 다음과 같이 표현할 수 있을 것이다.
(배열 인덱스 상으로는 (i+1, j+1)은 d[i][j]이다)
d[i][j] = d[i-1][j] + d[i][j-1]
그리고 시작지점인 (1,1)의 값은 1이 될 것이다.
배열 인덱스 상으로는 (1,1)은 d[0][0]이다.
d[0][0] = 1
그리고 웅덩이가 있는 곳은 절대로 갈 수 없는 곳이다.
웅덩이가 있는 위치 (i+1, j+1)은 갈 수 없기 때문에 0이다.
d[i][j] = 0
그 외의 위치는 0이 아닌 값으로 초기화해주자. 그러면 웅덩이인지 아닌지
구분할 수 있다.
그러면 어떻게 해야 할 지 정해졌다.
d[0][0]부터 d[m-1][n-1]까지의 값을 만들면 된다.
먼저 m x n 크기의 배열을 생성한 뒤, 각 배열의 값을 1로 초기화 해보자.
그리고 각 웅덩이의 좌표 값을 얻어온 뒤, 해당 위치의 값을 0으로 만들어준다.
그리고 d[i][j] = d[i-1][j] + d[i][j-1]을 시작지점을 제외하고 수행해주면 된다.
가장자리를 초기화 할 땐, 배열에서 벗어난 값을 참조하지 않도록 하자.
배열에서 벗어난 부분은 0이라고 간주하면 된다.
배열을 (m+1) x (n+1) 크기로 초기화 해서 범위를 벗어나지 않게 할 수도 있고,
자기 자신의 값과 왼쪽/위쪽의 값의 최솟값을 취해도 된다. 편한대로 하자.
위의 과정이 모두 끝났다면, d[m-1][n-1]의 값을 리턴하면 된다.
이 과정에서 주의해야 할 것이 하나 있다.
Integer나 Long Long으로는 경우의 수를 표현하려 해도 오버플로우가 일어날 수 있다.
그래서 문제에서 이야기 한 것이 하나 있었다.
1,000,000,007로 나눈 나머지를 리턴하자
하지만 경우의 수는 1,000,000,007를 넘어 셀 수 없을 만큼 커지고 있다. 나머지를 구하기 전에 이미 저장할 만한 공간이 터지려 하는데, 어떻게 해야 할까?
위의 경우의 수 계산을 약간 변형하면 된다.
d[i][j] = (d[i-1][j] + d[i][j-1]) % 1000000007
매 계산마다 1,000,000,007의 나머지를 저장하는 식으로 수행하면 된다.
위의 덧셈에서 1,000,000,007을 초과한 부분은 이제 관심이 없기 때문이다.
값이 매우 커질 때, 특정 값의 나머지를 리턴해야 할 경우 자주 쓰이는 방법이니
잘 기억해두도록 하자.
그러면 이를 코드로 표현해보자.
solution.cpp
#include <vector>
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
vector<vector<int>> d(m, vector<int>(n, 1));
for (vector<int> vi : puddles)
d[vi[0]-1][vi[1]-1] = 0;
for (int i=1;i<m;++i) d[i][0] = min(d[i-1][0], d[i][0]);
for (int i=1;i<n;++i) d[0][i] = min(d[0][i-1], d[0][i]);
for (int i=1;i<m;++i)
{
for (int j=1;j<n;++j)
{
if (d[i][j])
d[i][j] = (d[i-1][j] + d[i][j-1]) % 1000000007;
}
}
return d[m-1][n-1];
}
만약 문제에서 정답의 값이 매우 커질 수 있으니, 특정 값으로 나눈 나머지를 리턴하라
라는 말이 보인다면, 정답을 도출하는 과정에서 값이 오버플로우가 될 거라는 생각을
반드시 가지고 있어야 한다. Python이라면 오버플로우 문제는 없을 것이다.
위의 방법에서, d[i][j]로 가는 경우의 수를 알기 위해 d[i][j-1]과 d[i-1][j]의 경우의 수를 이용했다. 즉, 특정 위치로 가는 방법의 답을 재활용하여 또 다른 답을 도출하였다라고 볼 수 있다.
이런 방법론을 동적 계획법(Dynamic Programming - DP)라고 부른다.
알고리즘 문제로 종종 출제되는 방식이니, 익숙해지도록 해 보자.
프로그래머스에의 고득점 kit에서도 7문제를 배정할 정도이다.
Comments