[PS] 등굣길

문제

프로그래머스

집에서 학교로 가는 최단거리의 경우의 수 구하기

 

풀이

해당 문제는 프로그래머스 알고리즘 고득점 Kit의 레벨 3 문제이다.

dp 문제는 구현은 생각보다 어렵지 않고, 점화식을 세울 때 고민을 많이 해야 한다.

이번 문제는 난이도가 높지는 않았지만 헷갈리는 부분이 조금씩 있었다.

 

1. 규칙 찾기

아래의 입출력 예시를 살펴보자.

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

 

점화식을 세우기 위해 규칙을 찾아보았다.

처음엔 해당 지점까지 가기 위해 움직인 횟수를 전부 세야 한다고 생각했는데, 규칙이 보이지 않았다.

 

이후 해당 위치에 가기 위한 경우의 수로 접근해서 구해보았다.

[풀이 그림]

위 그림에서 각 칸마다 우측 상단에 써놓은 검은 숫자가

해당 위치로 갈 수 있는 최단 경로의 경우의 수이다.

*(2, 2)는 현재 puddles로 주어졌으므로 0을 써놓았다.

 

현재 위치에서 오른쪽과 아래쪽으로만 움직일 수 있으므로 아래와 같이 구할 수 있다.

1. (1,1) 집에서 시작
집에서 시작하는 경우의 수는 1개이다.

2. (1, 2)
(1, 2)에 도달하기 위해서는 (1, 1)에서 오른쪽으로 이동해야 한다.
따라서 (1, 2)에 도달하기 위한 경우의 수는 (1, 1)에서 오른쪽으로 가는 경우의 수 1개이다.

3. (2, 1)
(2, 1)에 도달하기 위해서는 (1, 1)에서 아래로 이동해야 한다.
따라서 (2, 1) 에 도달하기 위한 경우의 수는 (1, 1)에서 아래쪽으로 이동하는 경우의 수 1개이다.

4. (2, 2)
(2, 2)에 도달하기 위해서는 (2, 1)에서 오른쪽으로 이동하거나, (1, 2)에서 아래쪽으로 이동해야 한다.
따라서 (2, 2)에 도달하기 위한 경우의 수는 (2, 1)과 (1, 2)로 가는 경우의 수를 더한 2개이다.

5. 마지막 (4, 3)
(4, 3)에 도달하기 위해서는 (4, 2)에서 오른쪽으로 이동하거나, (3, 3)에서 아래쪽으로 이동해야 한다.
따라서 (4, 3)에 도달하기 위한 경우의 수는 (4, 2)와 (3, 3)으로 가는 경우의 수를 더한 4개이다.

 

2. 점화식 세우기

현재 위치에서 오른쪽 또는 아래쪽으로만 움직일 수 있으므로

생각보다 간단하게 규칙을 찾을 수 있었다.

dp[i][j] = dp[i-1][j] + dp[i][j-1] (dp[i][j] != puddles)

 

점화식은 위와 같이 나오고, i와 j의 범위에 주의하면 된다.

그리고 웅덩이 여부도 빼먹지 않고 생각한다.

 

코드

1. m x n 배열 만들기

m x n 배열이 주어지면 가끔 row와 column을 혼동하게 된다.

가로 길이가 m이고 세로 길이가 n이면, 열이 m개가 되고 행이 n개가 된다.

따라서 벡터는 dp[m][n] 같은 순서가 아닌, dp[n][m]으로 세우는게 정석임을 생각한다.

반대로 해도 되지만, 착오가 생기지 않게 확실하게 하는 편이 낫다.

// 가로가 m, 세로가 n 이면 열이 m개, 행이 n개이다
vector<vector<int>> dp(n+1, vector(m+1, 0)); // m x n 배열

 

또, 집의 좌표는 (1, 1)에서 시작되므로 +1씩 해주는 것에 주의한다.

 

2. 웅덩이 판별하기

웅덩이에서 나가는 경우의 수는 0개이다.

단순하게 생각해서 웅덩이의 dp[i][j] = 0으로 입력하면 큰 실수이다.

처음 시작 값에 dp 안의 요소들을 모두 0으로 초기화 했으므로, 이는 웅덩이와 구분되지 않는다.

 

따라서 웅덩이를 구분할 수 있는 값인 '-1'을 초기값으로 넣어주고,

추후 for문에서 -1을 0으로 변환하는 방식으로 구현했다.

for (auto p : puddles){
    dp[p[1]][p[0]] = -1;
}

 

3. 제출한 전체 코드

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    // 가로가 m, 세로가 n 이면 열이 m개, 행이 n개이다
    vector<vector<int>> dp(n+1, vector(m+1, 0)); // m x n 배열
    
    // 집 (시작점)
    dp[1][1] = 1;
    
    // 웅덩이
    for (auto p : puddles){
        dp[p[1]][p[0]] = -1;
    }
    
    // dp 구하기
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (i == 1 && j == 1) continue;
            if (dp[i][j] == -1) {
                dp[i][j] = 0;
                continue;
            }
            
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
        }
    }
    
    return dp[n][m];
}

 

회고

제출 전에 문제를 꼼꼼히 읽도록 해요....

 

문제 조건으로 주어진 1,000,000,007을 고려하지 않고 작성한 코드..

정확성 100%, 효율성 0%가 나왔다.

정답으로 치기도 애매하고 답으로 치기도 애매해서 PS 스터디에서 벌금을 내게 됐다.

 

벌금은 둘째 치고, 실제 코딩 테스트에서 이런 실수를 했다고 생각하면...

너무 너무 끔찍해서 3000원으로 끝난 것에 고마워하게 됐다.