맞는 분석입니다. 다만 BFS를 썼냐 안 썼냐가 중요한 게 아니라 DP를 했냐 안 했냐가 더 근본적인 차이를 불러일으킵니다.
시간복잡도 분석을 해 보면, DP를 하지 않는 경우 리턴값에 항상 1이 더해집니다. 따라서 왼쪽 위에서부터 출발해서 생성할 수 있는 모든 경로의 수가 시간복잡도의 lower bound가 됩니다. NxN 배열 + 모든 칸에 1이 적혀 있을 경우 리턴값은 2N C N ~ (2N!)/(N!N!)이 나옵니다. 1을 (2N!)/(N!N!)번 더하니 당연히 어마어마하게 느릴 수밖에 없습니다.
주목할 만한 사실은, BFS와 비슷한 접근방식으로도 충분히 DP를 돌릴 수 있다는 것입니다. 위상 정렬의 아이디어를 사용합니다. 위상 정렬을 하는 법으로 재귀를 사용하는 방법도 있고 queue를 사용하는 방법도 있는데, 이때 queue를 사용하는 방법이 BFS와 상당히 비슷합니다. 핵심 아이디어는 BFS와 비슷하게 알고리즘을 돌리되, 어떤 칸 v로 향하는 non-visited 칸이 더 이상 없을 때에만 visited[v] = true를 체크하고 queue에 넣는 것입니다. 이렇게 하면 각 칸을 방문할 때마다 해당 칸으로 향하는 경로의 개수가 몇 개인지를 결정할 수 있게 됩니다. 따라서 tabulation으로 DP를 할 수 있습니다.

blak1002 3년 전 9
해당 문제에서 주어진 map 사이즈가 100 * 100이고,
주어진 간선도 거의 노드당 2개씩이라고 감안하고 본다면,
인접리스트의 시간복잡도 O(V+E)라고 생각해보면
최대 연산 수가 100 * 100 + 2 * (100 * 100) == 3만
이라고 생각해서 1억에 상당히 못미치는 수기 떄문에
시간복잡도는 BFS돌리기에 충분하다는 생각에 BFS로 접근해서 풀었다.
하지만 메모리 초과가 나왔는데
추측건데 아래의 이유가 원인이지 않을까 생각해 봤다.
상당히 BFS스러운 문제지만 BFS로 풀면 메모리 초과가 나온다.
이유는
보통 BFS로 풀이가 가능한 문제들에서는 현재 Node 근방에 연결된 Node에서
약간 곰팡이가 퍼지듯 주변 노드를 탐색하는 방식(상,하,좌,우 탐색)으로 탐색이 되는데
이런식으로 탐색을 하다보면 무조건 재방문하는(겹치는 탐색 부분) 노드가 생긴다.
그래서 재방문을 막고자 각 Node를 방문한 뒤, isVisited와 같은 배열에
방문 여부를 체크해 둠으로써 중복된 방문을 방지하는 방식으로 풀이된다.
이렇게 하면 지금 문제에서 주어진 100 * 100 사이즈의 map이라도 풀이가 가능한
문제들도 많다.
심지어 토마토 문제는 100 * 100 * 100 사이즈인데도 BFS로 풀린다.
(https://www.acmicpc.net/problem/7569)
하지만 이 문제에서 정답으로 원하는 값은
"가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수"
즉, 같은 Node를 밟았다 하더라도 현재 Node 이전에
어떤 Node를 밟았는지에 따라 다른 경우로 여겨지기 때문에
isVisited와 같은 배열에 방문 여부를 체크하고, 재방문을 막아서는 안된다.
그래서 이번 문제에서 BFS를 사용하려면 그냥 중복방문을 다 포함하면서
가장 오른쪽 아래 칸에 도달하는 수를 count하는 방식으로 풀 수 밖에 없는데.
map의 사이즈가 작은경우라면 문제가 되지 않지만,
만약 모든 칸에 값이 1이고, 100 * 100 사이즈의 Map이라면
과장 좀 보태서 Queue에 2^N에 가까운 너무 많은 Node가 들어가기 때문에
(같은 칸의 Node도 중복되게 포함되어 있음으로)
메모리 초과가 나는 것으로 보인다.
그래서 재방문을 막을 수 있는 DP + DFS 조합으로 풀거나,
아예 DP식 풀이로 접근하는게 옳은 접근으로 보인다.
+ 오른쪽과 아래로 이동할 수 밖에 없다는 조건이 보이면
BFS 말고 DP로도 풀 수 있지 않을까? 하는 생각을
가져보도록 해야겠다.
=============================================================================
혹시 위 내용에 잘못된 접근이 있다면 알려주시면 감사하겠습니다 : )