백준 - 내리막 길

문제 출처: https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

초기 기획

N, M의 범위가 크므로 DFS보다는 BFS를 사용하는 것이 더 좋다고 판단했다. 목적지에 도착할 때까지 방문 체크를 하고, 다른 길을 통해 이동하다가 방문된 곳을 만나면 더 이상 진행시키지 않고 이동 가는 한 길 +1을 해주었다.

이 방법으로 진행 하니 '메모리 초과' 에러가 발생하였다.

 

최종 기획

메모이제이션이 필요하다는 것을 파악했다. 결국 DP+DFS가 사용되어야 한다.

 

처음에 도착하고 나면 배열이 위와 같이 설정된다.

여기서 필자는 copy라는 2차원 배열을 만들어서 사용했다.

 

다음에는 다른 방향으로 이동하였을 경우다. 여기서 1,4 위치에서 다시 한번 분기하여 다른 방향으로 재귀를 돌게 된다.

 

마지막 길을 통해 이동하였을 때의 copy배열의 모습이다.