>>>>>>>>>>>>>>>>>>> https://www.acmicpc.net/problem/1520


-1로 초기화 해놓고 방문 표시로 0을 찍는 거랑 초기화 안하고 탐색하는 방법의 차이는 무엇일까?




36 35 34 

35 34 33 

34 33 100


이런 맵이 있다고 가정해보자


오른쪽 맨 아래에 도착해야 하지만 높아서 도착할 수가 없다





1. 0으로 초기화 했을 때


그렇다면 dp 배열은


0 0 0

0 0 0

0 0 0


으로 초기화 돼있을 것이다.


재귀함수의 코드는 다음과 같다


static int dfs(int x, int y) {

if (x == n-1 && y == m-1) 

return 1; // 목적지 도착시

if (dp[x][y] != 0)

return dp[x][y]; // 값 갱신시

for (int i=0; i<4; i++) {

int a = x + mx[i];

int b = y + my[i];

if (0<=a && a<n && 0<=b && b<m && map[x][y] > map[a][b]) {

dp[x][y] += dfs(a,b);

}

}

return dp[x][y];

}


목적지에 도착하면 경우의 수1을 return 시키고 dp 배열에 메모한다!


만약 dp배열에 메모가 안됐다면 dfs를 통해 메모하고 return 시킨다.


답은 잘 나온다... 하지만 쓸데없는 계산이 많다...


왜냐하면 목적지에 도착할 수 없으므로 dp배열은 항상 0으로 가득찰 것이다.


그리고 0이 아니기 때문에 항상 4방향 탐색을 해야만 한다... 이미 방문한 곳인데도 말이다!


아직까진 무슨말인지 정확히 이해는 안갈 것이다. 밑에서 설명하겠다.


그렇다면 방문 표시를 해주자



2. -1로 초기화 했을 때


그렇다면 dp 배열은


-1 -1 -1

-1 -1 -1

-1 -1 -1


으로 초기화 돼있을 것이다.


static int dfs(int x, int y) {

if (x == n-1 && y == m-1) 

return 1; // 목적지 도착

if (dp[x][y] != -1)

return dp[x][y]; // 방문을 했었다면

dp[x][y] = 0; // 방문을 안했다면 0으로 만들어서 dfs한 값을 저장

for (int i=0; i<4; i++) {

int a = x + mx[i];

int b = y + my[i];

if (0<=a && a<n && 0<=b && b<m && map[x][y] > map[a][b]) {

dp[x][y] += dfs(a,b);

}

}

return dp[x][y];

}


목적지까지 가기위해 자기가 지나온 길을 0으로 만들면서 뚫고 간다!


그렇다면 중간 진행 상황을 dp배열을 통해 한 번 봐보자!


0  0  0

0  0  0

-1 0 -1


이미 (1,1)을 방문했었던 흔적이 있다.


상황은 (1,1)에서 더 나아가느냐, 물러서느냐로 나뉜다!


좌표 (1,1)에서 map 상태는 다음과 같다


35 34 33

34


(1,1)지점의 값은 34이다.


dp 배열에는 (1,1) == 0이다.


즉 이미 방문을 했었다는 소리, if (dp[1][1] != -1) return dp[1][1]에 의해서


호출한 함수로 돌아간다 ( (1,1) -> (1,0) )


그리고 (1,0) -> (2,0) 으로 다시 파고 들어간다.





... 하지만 0으로 초기화 하고 다 진행한다면? dp배열은 목적지에 도착한 적도 없기 때문에 값이 다 0이다.


35 34 33

34


위 상황에서 (1,1)에 있다고 똑같이 가정했을 때 dp[1][1] = 0 이기 때문에


if (dp[1][1] != 0) return dp[1][1]; 조건문에 들지 못하고


또 한 번 4방향 탐색에 들어가 


(1,1) -> (1,2) 탐색에 들어가버리게 되는 것이다.


방문한 곳은 이미 거기서 갈 수 있는 경로를 저장해놨기 때문에 또 방문할 필요가 없다.


그래서 -1로 초기화를 하면 방문 표시도 함께 하면서 경로 수도 같이 저장하기 때문에


불필요한 탐색을 줄이지만


0으로 초기화된 dp를 이용하면 지금 있는 곳이 방문한 위치인지 아닌지 모르기 때문에


또 4방향 탐색을 진행해야한다.


그러므로 -1로 꼭 초기화를 해주자!