topology   4년 전

단계별로 풀어보기를 하다가 DFS BFS 탭에서 이 문제를 만났습니다. 경로의 개수가 263-1 이하라는 말을 보고 DFS나 BFS로 풀면 터질 것 같아서 일단 DP로 풀기는 했습니다만, 혹시 DFS나 BFS로 푸는 방법이 있나 해서 질문합니다.

lsc4719   4년 전

격자를 A라고 할 때요,

A(i, j) : 격자 A의 i번째 행, j번째 열에 위치한 칸의 값 (1<=i<=높이, 1<=j<=너비)

라고 하면, 이와 동일한 형태의 DP 표를 만들었다고 생각하면요,

DP 점화식을 풀기 위한 표를 B(i, j)라 하면,

B(i, j)를

(1, 1) -> (1, 2), (2, 1) -> ... 이런 식으로 채워나가게 될 때,

각각의 순서쌍을 어떤 그래프 G의 노드가 갖는 값이라고 생각하면,

DP 표를 채워나가는 것이 G에서의 BFS traversal과 동일하므로,

그렇게 분류한 게 아닐까? 하고 미루어 짐작해봅니다. ㅎㅎ

topology   4년 전

음.. 그럴 듯하네요.

댓글을 작성하려면 로그인해야 합니다.