ChessMetric

문제

킹 나이트는 킹 + 나이트 만큼 움직일수 있는 말이다

체스판의 크기 size 와 킹 나이트의 시작위치 start 와
최종위치 end 가 주어진다

정확히 numMoves 회만에 도착하는 방법이 얼마나 있는지 리턴한다

• 경로가 다르다면 다른 방법
• 같은 칸을 반복해서 이동하는 것도 ok
  (start 나 end 도 중복해서 이동가능)

예시 입력

3, {0,0}, {1,0}, 1
3, {0,0}, {1,2}, 1
3, {0,0}, {2,2}, 1
3, {0,0}, {0,0}, 2
100, {0,0}, {0,99}, 50

예시 출력

1
1
0
5
243097320072600

생각의 변화

E로 가는 경로

거꾸로 E로 가기위해 numMoves-1 에 있어야 하는 위치

S에 도달하려면

공식이 있는지 체크해보았는데, 머리만 아프고 유의미한 법칙은 나오지 않았다

Map 을 만드는 게 나을까?..
이동기억이 필요하다

No.
기억해야 하는건 현재 얼마나 움직였는지와 현재 좌표뿐

pseudo code

howMany(size, start, end, numMoves)
    dfs(0, end[0], end[1], size, start, numMoves);
    
k_r[8] = -1, -1, -1, 0, 1, 1, 1, 0
k_c[8] = -1, 0, 1, 1, 1, 0, -1, -1

l_r[8] = -2, -2, -1, 1, 2, 2, 1, -1
l_c[8] = -1, 1, 2, 2, 1, -1, -2, -2

dfs(n, r, c, size, start, numMoves)
    if r < 0 || r >= size || c < 0 || c >= size
        return 0
        
    if n == numMoves
        if r == start[0] && c == start[1]
            return 1
        else
            return 0
            
    long long ret = 0
    
    for i=0  i<8  i++
        ret += dfs(n+1, r+k_r[i], c+k_c[i], size, start, numMoves)
    
    for i=0  i<8  i++
        ret += dfs(n+1, r+l_r[i], c+l_c[i], size, start, numMoves)
        
    return ret

마지막 예제 시간초과

모든 경우를 깊이우선탐색 해서일까, 마지막 예제가 2초를 넘긴다

생각의 변화

전체 경우를 깊이 우선 탐색하면 호출스택이 너무 깊어진다

for loop 으로 대체

각 스탭별로 히스토리가 필요
자연스러운 구조

중복되거나 어색하지 않은

좌표 필요
move 도 필요

3차원 배열
이제 이 좌표에 올때 얼마나 걸렸는지
걸린 거리별로 히스토리가 구분된다 good

시작 위치가 (0,0) 이 아니면?

상관없다
진짜 괜찮나?...

맨 위에서 numMoves 만큼 도니까 괜찮다

더해야 한다 +=

pseudo code

move_r[16] = -1, -1, -1, 0, 1, 1, 1, 0, -2, -2, -1, 1, 2, 2, 1, -1
move_c[16] = -1, 0, 1, 1, 1, 0, -1, -1, -1, 1, 2, 2, 1, -1, -2, -2

long long ways[100][100][51]

howMany(size, start, end, numMoves)
    ways[start[0]][start[1][0] = 1
    
    for i=1  i<=numMoves  i++
        for r=0  r<size  r++
            for c=0  c<size  c++
                for j=0  j<16  j++
                    nr = r + move_r[j]
                    nc = c + move_c[j]
                    
                    if (nr < 0 || nr >= size || nc < 0 || nc >= size)
                        continue
                        
                    ways[nr][nc][i] += ways[r][c][i-1]
                    
    return ways[end[0]][end[1]][numMoves]