[Algorithm] Programmers :: 보행자 천국

https://school.programmers.co.kr/learn/challenges?order=recent&statuses=unsolved&levels=3&languages=cpp 

코딩테스트 연습 | 프로그래머스 스쿨

#define MOD 20170805;
 
int dp[502][502][2];
 
int solution(int m, int n, vector<vector<int>> city_map) {
    long long answer = 0;
    
    // 시작위치는 자유이동이니까 두 방향 다 1을 넣어놓는다.
    memset(dp, 0, sizeof(dp));
    dp[1][1][0] = 1;
    dp[1][1][1] = 1;
 
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (city_map[i - 1][j - 1] == 0) // 자유이동.
            {
                dp[i][j][0] = (dp[i][j][0] + dp[i][j - 1][0] + dp[i - 1][j][1]) % MOD;
                dp[i][j][1] = (dp[i][j][1] + dp[i][j - 1][0] + dp[i - 1][j][1]) % MOD;
            }
            else if (city_map[i - 1][j - 1] == 1) // 이동금지.
            {
                dp[i][j][0] = 0;
                dp[i][j][1] = 0;
            }
            else // 왔던 방향과 동일한곳으로만 이동가능.
            {
                dp[i][j][0] = dp[i][j - 1][0] % MOD;
                dp[i][j][1] = dp[i - 1][j][1] % MOD;
            }
        }
    }
 
    return dp[m][n][0] % MOD;
}

첫시도는 BFS로 해봤다. 시간초과가 나왔다.

사실 BFS로 코드작성하면서 '카카오 3레벨이 이렇게 쉬울수가 없는데'라고 생각했건만, 역시 시간초과가 떴고 바로 DP문제라고 결론지었다.

 

시작지점부터 오른쪽,아래로만 이동가능하다는 조건을 보고 이전에 풀었던 쓰레기로봇 문제랑 연결지어서 로직을 생각해보려했지만, 특정 조건들때문에 (1이면 이동불가능,2면 왔던 방향을 유지해야 이동가능) 정답을 생각해내지 못했다.

다른 사람 풀이를 보고나서야 이해를 할 수 있었다.

 

일단 '방향'이라는 조건이 있기 때문에 DP테이블을 3차원으로 선언한다. 

그리고 시작지점은 반드시 0이기 때문에 (자유이동) 시작지점의 오른쪽,아래 dp값 둘 다 1로 미리 넣어준다.

여기서 dp[0][0][0]의 값이 의미하는 바는, 0,0에서 오른쪽으로 갈 수 있는 경우의 수를 말한다.

마찬가지로 dp[0][0][1]은 0,0에서 아래로 갈 수 있는 경우의 수를 말한다.

 

본격적인 로직으로는, city_map[i][j]가 0일 경우, 즉 자유이동이 가능할 경우 아래와 같다. (MOD연산은 일단 뺐다)

dp[i][j][0] = dp[i][j][0] + dp[i][j - 1][0] + dp[i - 1][j][1];
dp[i][j][1] = dp[i][j][1] + dp[i][j - 1][0] + dp[i - 1][j][1];

 

시작지점부터 차근차근 업데이트하기때문에 기본적으로 둘 다 자기자신을 누적에 포함한다.

그리고 각자 윗좌표의 아랫방향dp값과, 왼쪽좌표의 오른쪽방향 dp값을 누적에 포함한다.

city_map[i][j]가 0이라면, 어떤 방향에서 오든 이동이 가능하기 때문이다.

 

city_map[i][j]가 1일 경우, 해당 좌표의 dp값을 0으로 고정한다. 해당 좌표에서는 위로든 아래로든 더이상 뻗어나갈 수 없기 때문이다.

 

city_map[i][j]가 2일 경우, 각 방향의 반대방향좌표의 값을 그대로 계승한다.

즉, dp[i][j][0]에다가 값을 업데이트하려할 경우, dp[i][j-1][0]의 값을 그대로 계승한다.

왜냐하면 현재좌표에서는 이전방향 그대로를 유지해서 이동이 가능하기 때문이다.

 

다시 인지해야할 것은, dp[i][j][0]은 i,j에서 오른쪽으로 가는 경우의 수란걸 잊지말자.

그렇기 때문에 dp[i][j][0]의 값을 업데이트하기 위해선, 오른쪽으로 가는 경우의 수를 업데이트해야하니 바로 왼쪽좌표의 오른쪽으로 가는 경우의 수를 계승하는 것이다.

 

 

 

 

DP 문제 너무 어렵다.