#1520 내리막길

알고리즘 핵심:

백트래킹! 계속 dfs,bfs로 문제를 풀다가 오랜만에 dp를 활용한 백트래킹 방법을 적용하였습니다.

DFS를 통해 목적지까지 탐색하였고 탐색을 하면서 방문(visit[x][y]>=0)표시를 해나갔습니다.

그 후 목적지인 오른쪽 하단에 도착하면 1을 리턴하였고  범위를 벗어나는 영역은 0을 리턴하였습니다.

그 외에 방문이 돼 있는 지역이 next x,y로 선정이 되어 재귀함수를 통해 x,y가 된다면 방문이 돼 있는 지역이므로 백트레킹을 적용하여 그떄의 visit[x][y](이전의 visit[nx][ny]값이라고 보면 됨) 를 리턴하였습니다.

그리고재귀를 통해 백트래킹을 적용한 함수 호출하는 부분은 visit[x][y]=visit[x][y]+dfs(nx,ny)이렇게 설정하면 백트래킹을 하면서 0,1,visit[nx][ny]인 부분을 다 적용하며 원점으로 거슬러 올라가게됩니다.

 

그리고 함수가 끝나는 마지막에 visit[x][y]를 리턴하게 되면 결국 처음에 준 입력값 x=0,y=0 즉 visit[0][0]값을 리턴하게 됩니다. 실행 화면을 통해 백트래킹을 좀 더 자세히 보면 다음과 같습니다. 매 함수가 호출 될 떄마다 visit를 출력해 보았습니다. 왼쪽 위에서부터 아래로 -> 오른쪽 순서입니다.

소스코드