1513 문제에서 왜 4차원 배열을 사용해야 하나?

개인적인 공부를 위해 쓴글이므로 이해가 안될 수도 있습니다.

 

처음에 문제를 보고 DP 배열을 3차원으로 정의했다.

 

DP[c][n][m]  이렇게 정의하면, c가 0일 때 경우의 수를 먼저 구해놓고, c가 1일 경우 DFS로 계속 탐색하다가 오락실을 만나면 다음 호출부터는 c를 0으로 만들어 [0][y][x]를 탐색하는데, 만약 dp[0][y][x]가 이미 갔던 곳이면 해당 값을 리턴하고 아니면 지속적으로 탐색하도록 하는 방법을 생각했다. 지금까지는 논리적으로 문제가 없어보인다. 하지만, c가 2가 되면은 반례가 보인다.

 

문제에서 주어지는 예제로 한번 생각해보자.

3 3 2
2 2
3 2

 

그럼 c가 1일 때 해당하는 경우의 수는 3개이다.

(1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)
(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)

 

 

이제, c가 2일 때를 생각해보자. 위에서 오락실을 만나면 다음 호출부터는 c를 -1한다고 했다. 그럼 (2, 2)나 (3, 1)을 만난 다음 순간부터는  dp[1][y][x] 로 호출하게 되는데, 만약 1번째 오락실 위치에서 (r, c+1)인 (2, 3)을 호출했다고 해보자.

 

dp[1][2][3]은 1이 지나는 경우의 수인 2가 저장되어 있으므로 실제로 2개의 오락실 모두를 지나는 상황이 일체 일어날 수 없는 좌표임에도 2개의 경우의 수가 추가되어버린다. 즉, 3개의 변수로 만든 3차원 DP 배열로는 해당 좌표가 몇 번째 오락실이 지나갔는지를 판단하는 기준이 없기 때문에 자기 자신이 지나간 길임에도 경우의 수에 더해지는 것이다.

 

그래서 4차원 DP 배열로 만들어 c의 상태에 따라 i번째 오락실이 지나간 경우의 수를 저장해주는 것이다. 그러면 c가 2일 때 1번째 오락실을 밟고 다음 호출인 (2, 3)은 c가 1, 최근 밟은 오락실 번호가 1이 되어 호출된다. 그럼, dp[c=1][prev=1][y=2][x=3] 는 애초에 갱신되지 않은 값이므로 dp[c=1][prev=1][3][3] 까지 호출되고 여기서 c가 0이 아니기 때문에 0을 반환하여 경우의 수에 영향을 주지 않는다.

 

반대로 dp[c=1][prev=1][y=3][x=2] 인 경우로 갔다면 현재 당장 dp에 값이 저장되어 있지 않아 탐색을 더 시작하지만, 다음 호출부터 dp[c=0][prev=2][y=3][x=3] 와 같이 c가 0일 때 2를 통해 지나간 경우의 수 즉, c가 1일 때 2를 통해 갈 수 있는 경우의 수를 반환하게 되므로 결국 오락실1과 중복되지 않는 길을 갈 수 있게된다.