본문 바로가기

카테고리 없음

[백준 18287번] 체스판 이동 (Python3)

mod = 10**9+7

def multiply(A,B):
  S = [[0]*len(B[0]) for i in range(len(A))]
  for i in range(len(A)):
    for j in range(len(B[0])):
      for k in range(len(B)):
        S[i][j] += A[i][k]*B[k][j]
      S[i][j] %= mod
  return S

def cal(A,n):
  if n==0:
    return [[int(i==j) for j in range(M)] for i in range(M)]
  if n==1:
    return A
  c = cal(A,n//2); c2 = multiply(c,c)
  return multiply(c2,A) if n%2 else c2  

N,M = map(int,input().split()); N-=1
matrix = cal([[int(abs(i-j)<3)+int(j==i and 0!=j!=M-1) for j in range(M)] for i in range(M)],N//2)
print(0 if M==1 and N else sum(map(sum,multiply(matrix,[[1+int(N%2 and 0!=i!=M-1)] for i in range(M)])))%mod)

인접행렬 경로 문제

일하는 세포 [백준 17401번] 일하는 세포 (Python3) (tistory.com) 나 길의 개수 [백준 1533번] 길의 개수 (Python3) (tistory.com) 와 비슷한 방식으로 해결할 수 있다.

 

풀이를 설명하면,

1. 홀수번째 행과 짝수번째 행을 하나의 묶음으로 생각한다.

2. 1에서 묶었을 때 각 칸에 대해서 경로에 대한 행렬을 생성한다. 즉, 현재 칸에서 2행 밑으로 내려갈 때 갈 수 있는 칸 +1을 해주면 된다.

3. 분할정복을 통한 거듭제곱으로 경로의 개수를 세어준다.

4. 만약 N-1이 홀수인 경우 (N-1인 이유는 마지막 행에서는 이동하지 않으므로) 마지막 행이 두개로 묶을 수 없기 때문에 따로 취급해서 한번 더 경로에 대한 행렬곱셈을 해주어야한다.

5. M이 1인 경우 0을 출력해야 한다. 이때 N도 1인 경우에는 1을 출력해야한다.

 

5번의 예외처리 때문에 약간 까다로웠던 문제였다. 풀이 자체는 인접행렬에 익숙하다면 금방 생각해낼 수 있다.

 

 

여담) 내 풀이가 숏코딩 순위 1위가 되었다.