[알고리즘] 백준 1890번

[알고리즘] 백준 1890번

문제

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

---

풀이

오늘도 역시 BFS/DFS 문제를 풀어보았습니다. 이 문제를 처음 봤을 때 여타 다른 문제와 다를 것이 없다고 생각했고 BFS를 이용해서 풀면 쉽게 풀릴 것이라고 생각했습니다. 그리고 BFS로 코드를 작성하고 실행시켜보니 역시 원하는 출력 결과물이 나왔습니다. 하지만 사이트에 제출하니 시간 초과라는 문구가 떴습니다. 그제서야 깨달았죠! 단순히 BFS/DFS로 풀면 안되겠구나! N이 100이 된다면 상당히 많은 칸을 점프할 것이고 그 중 중복 탐색이 생길 수 있다는 것을 알게되었습니다. 그렇기 때문에 BFS/DFS와 DP를 같이 사용해야하는 다소 복잡한 문제였습니다.

다음은 저의 풀이 과정입니다.

1. 처음에는 BFS를 사용하여 풀었으나 시간초과가 났습니다.
2. 이후 중복 탐색을 막기 위해 이미 방문한 점이고 이전의 해당 점에서 탐색한 이력이 있다면 해당 이력을 바탕으로 중복 탐색을 하지 않고 값을 알아내려고 했습니다.
3. 저는 그래서 목적지인 (N-1, N-1)을 1로 주고 이를 활용하여 점프를 통해 해당 점에 도달했을 때 백트래킹하면서 목적지까지 오는데 들린 점들에 적절한 값을 할당해주었습니다.

먼저 시간초과가 난 BFS 탐색 코드입니다.

코드 자체는 여타 다른 BFS코드와 다를 것이 없지만 위에서 언급하였듯이 중복 탐색의 가능성이 있기 때문에 올바르지 않은 코드입니다.

다음은 DP와 DFS를 활용한 코드입니다.

1. 목적지의 값을 1로 할당합니다.
2. 만일 목적지에 도달했으면 return합니다.
3. 현재 점에서 점프해서 도달하는 점이 0이라면 그 뜻은 아직 해당 점은 방문한 적이 없다는 뜻이고 만일 0이 아닌 값이 존재한다면 해당 점을 통해 목적지에 도달한 이력이 있다는 뜻입니다.
4. dfs 함수가 return되면, 즉 백트래킹된다면 현재 지점의 값을 돌아가야할 이전의 지점의 값에 더합니다. 이런 과정을 통해 해당 점에서 목적지까지 가는 방법의 갯수를 확인할 수 있습니다.
5. 그렇게 탐색했던 경로들을 모두 백트래킹하게 되어 취합된 합은 결국 시작점에 할당이 되고 시작점의 값이 곧 목적지까지 가는 방법의 갯수라고 할 수 있습니다.

---

배운점

1. BFS/DFS 탐색을 할 때도 중복 탐색에 대한 경우를 생각해야하는 문제가 있다