[AC] 1520 내리막길

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2017.05/1520.cpp

이 문제는 1년전에 틀렸던 문제였다. 결론만 보자면 매우 간단한 문제이다. 아마 1년전에 틀렸던건 작년 초에 내가 메모이제이션을 정의하지 못했던 시절인것 같다.

물론 너무 오랜만에 문제를 풀다보니 오래걸렸다.

먼저 문제의 요점을 파악해보자면 현재보다 낮은 지점으로 가야하고, 최대크기가 500x500이라는 것이다. 높이가 1만이라는건 크게 개의치 않아도 될 것 같다.  뿐만 아니라, 정답이 10억이하의 음이아닌 정수라고했으니 int범위안에 정답이 있을 것이다. 

그럼 이제 문제의 풀이를 보자.

500x500.. 적다면 적고 크다면 큰 매트릭스이다. 아마 일반적 dfs로 접근하면 시간초과가 날 확률이 매우 높다.(그래서 1년전에는 시간초과를 맞았다.)

그래서 BFS로 풀어보니 메모리가 너무 커지는 문제가 발생한다. (큐가 너무 커지는 문제..)

그래서 우리에겐 메모이제이션 개념이 있는것이다. 이미간 지점에 대해서는 더이상 계산을 하지않게 하는 방법!

이방법을 사용한다면 위의 두 문제를 해결할수있다. 나는 DFS로 풀었다.

먼저 memo를 할 배열을 만들고 -1로 전부 초기화를 한다. 이건 가지 않았다는 말이다.

그리고 dfs를 돌면서 만약 이 지점이 이미 값이 있다면 바로 리턴을 한다. 왜냐면 이미 방문한 지점에 대해서는 값이 갱신되어 있기 때문에 더이상 추가적인 계산이 필요없다. 어떤 점이든 정점에 다다르면 1을 리턴한다.

조금 더 풀이해보면 포문에

cnt+=dfs(nx, ny)라고 되어 있는데

이미 간 지점이라면 이미 이 지점에서 몇가지 경우의수로 도착을 하였다. 이걸 알려줄 것이고 없다면 쭉 돌다가 1을 리턴하니 이걸 추가할것이다. 즉 4방향에 대해서 모든 cnt가 더해진다.

그리고 최종적으로 해당 좌표의 cnt값이(목적지까지 가는 가짓수) 나올텐데 이를 memo에 기록해둔다. 그럼 각 지점마다 정점에 도달하는 수가 dfs를 통해 기록이 될 것이고 최종적으로 0, 0에서 출발하여 정점까지 다다를때의 경우의수가 기록되어 정답이 나오게 되는 것이다.

 메모이제이션은 참 간단한 개념이지만, 익숙해지는데 조금 걸리는것 같다. 하지만 한번 익숙해지면 참 써먹을 곳이 많고 특히!! sw회사 알고리즘 필기시험을 준비한다면 반드시 알아두어야 할 개념이다. 특히 삼성sw역량평가의 경우 2번문제에서 몇번 나왔었다. 일반적인 dfs, bfs로는 풀리지않고 메모이제이션을 써야 풀리는 경우. 

뭐 어쨌든 알고리즘은 많이 푸는게 장땡이다.