프로그래머스 등굣길

프로그래머스의 DP 쪽 문제 세번째이다. 2D 지도가 주어지고, 1,1에서부터 최우하단 좌표까지 가능한 경로의 개수를 구하는 문제이다. 여기서, 특정 위치가 웅덩이가 될 수 있다. 해당 웅덩이는 경로에 포함될 수 없다(지나갈 수 없다).

움직이는 패턴이 상하좌우가 아니라, 오른쪽과 아래쪽으로만 움직인다는 제약조건이 있다. 이 제약조건이 있어서 DP를 사용해 문제를 풀 수 있다고 한다. 부분의 최적해가 전체 최적해에 포함이 되기 때문에 DP를 사용할 수 있다...

 

정말 코드에서 엄청난 삽질을 했다. 처음에는 dfs와 섞은 솔루션을 작성했다. 이 문제와 비슷하게 접근해서 작성했는데, 계속 문제가 발생했다...

 

정확도 체크는 어느정도 맞는데, 효율체크가 우수수수... 틀려 다른 방법을 찾아봤다.

그냥 위에서부터 쭉 체크하면서 지나가도 되지않을까....? -오른쪽, 밑으로만 이동하니까, 그렇게 탐색하면 아직 탐색이 끝나지 않은 곳을 참조하지는 않을 것 같다.

dp[i][j] = i번째 행, j번째 열에서의 경로 수로 생각하고 접근했다. 어떤 좌표의 경로 수는, 자신의 위와 왼쪽 셀 경로 수의 합이다. 이러면 이제 DP 식 완성이다.

남은것은 가장자리 초기화(좌표를 1부터 시작하고, 나머지는 0으로 채운다.)와 초기값(1,1 은 1,0 이나 0,1 자리의 값을 가져오므로, 두 자리 중 하나만 1로 초기값을 넣어준다)만 설정하면 된다.

 

여기에 더해서, 웅덩이를 처리해준다. 처음에는 각 좌표를 받아 그 좌표가 웅덩이 집합에 들어있는지 확인했다. 이 방식을 사용하면 타임아웃이 뜬다. 웅덩이 좌표의 개수는 맵 크기와 비례하므로 너무 연산이 오래 걸린다.

초반에 map[][]을 선언해주고, 웅덩이를 해당 배열에 마킹해 탐색 중 웅덩이를 바로 확인할 수 있게 작성했다.

---

#include <string>
#include <vector>
#include <iostream>

int solution(int m, int n, vector<vector<int>> puddles) {
    // int answer = 0;
    // memset(g_dp, -1, sizeof(g_dp));
    // g_m = m;
    // g_n = n;
    // int res = dfs(0, 0, puddles);
    
    int map[101][101] = {0,};
    int dp[101][101];
    
    for (auto v : puddles)
        map[v[1]][v[0]] = -1;
    
    dp[1][0] = 1;
    for (int i = 1; i <= n ; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (map[i][j] == -1)
                dp[i][j] = 0;
            else
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
        }
    }
    return dp[n][m];
}

 

처음 접근을 다른 문제와 유사하게 했는데, 나중에 생각해보니 웅덩이 체킹이 너무 느렸던 것 같다. DFS를 같이 돌려도 괜찮지 않을까 싶은데, 어차피 움직일 수 있는 방법이 제약되어 있으니 이 방식이 제일 깔끔한 것 같다.

 

오늘도 평온한 하루가 되길. 슨민.