백준 1520. 내리막길

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

1520번: 내리막 길

 

상하좌우로 이동할수 있기 때문에 dfs로 모든 경우를 탐색해보면 된다. 

상하좌우 다음지점이 현재 지점보다 낮은수 즉 내리막길이면 이동한다.

그런데 그냥 모든 경우를 탐색하면 시간초과가 나게된다.

 

하나의 지점은 다음과 같이 3개의 상태를 갖는다고 볼 수 있다.

 

1. 아직 아예 방문 안해본 지점 // d[i][j] = -1 

2. 방문했지만 도착루트에 포함되지는 않는 지점  // d[i][j] = 0

3. 방문했고 도착루트에 포함되는 지점  // d[i][j] > 0 

 

d[i][j]는 (i,j)에서 도착지점 까지 갈수 있는 경우의 수.

d[][] 배열을 처음에 -1로 초기화한다.

그 후 이동할수 있는 다음 지점으로 이동하는데 만약 다음지점 (nr,nc)의 상태 즉 d[nr][nc]가 -1이라면 아직 방문 안해본 지역이므로 일단 방문하고 d[nr][nc] = 0으로 방문했음을 표시한다.

처음에 d 배열을 -1로 초기화하고 방문 시 0으로 표시하는 이유는 이미 방문했지만 도착 루트가 아닌 지점이 0을 리턴하도록 하기 위함이다.

그리고 d[r][c]  += dfs(nr, nc) 이런 식으로 현재 지점 r,c에서 갈수 있는 다음 지점들의 도착루트까지 가는 경로의 수를 더해준다.