[일반] 격자 조합문제 최단거리 아닌건 어케품?

[익명(119.203)]

예를들어서,

3*4 격자사각형 한귀퉁이에서 맞은편 귀퉁이까지

7번만에가 아니라 9번만에 가는건 어떻게 푸나요??

일반적인 방법이 있나요

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(119.203)]

고딩수준 넘어가도됨

[익명(175.223)]

재밌는 주제네 근데 어렵당

[llll(111.118)]

모든 칸에 k번째만에 도착하는 방법의 수를 세가면서 업데이트하면되지 약간은 비효율적이지만..

[익명(119.203)]

무슨 말인지 좀 자세하게 알려줄 수 있음? 이해가 안가네..

[Zadkiel(dhksrl215)]

격자를 전부 그래프로 보고 인접행렬을 만들면 될듯 비효율적이지만 확실한 방법

[익명(119.203)]

흠..그방법밖에 없을까?

[llll(118.235)]

인접행렬로보고 거듭제곱하는거랑 비슷한 말임 각 격자칸 (i,j)에 time t에 올수있는 경우의수 N(i,j,t)하면 점화식이 N(i,j,t+1)이랑 N(i+x,j+y,t)사이에 생기잖아 x,y=0,+-1에 대해서 이걸 모든칸(혹은 조금 더 생각하면 필요한칸들만)에 대해 t를올려가면서 업데이트하면돼

[llll(118.235)]

최단거리에서는 x,y가 0,-1인 특이한 경우라서 업데이트해야하는칸들이 굉장히 명확한 쉬운경우인거고

[llll(118.235)]

엄청쉽게 1×1에서 왼쪽위에서 오른쪽아래로 4번만에라구 생각하고 이걸 업데이트하면 t=0일때1 00 01일때0 11 02일때2 00 23일때0 44 04일때8 00 8이런거지뭐

[llll(118.235)]

아 이런 디씨 이게 다 깨지는구나.. 그냥 그려보면 무슨말인지 알수는잇을듯..

[ㄴㅇ(223.62)]

화살표 나열로 보면 될것 같기도