[백준 12850번] 파이썬 - 본대 산책2

백준 12850_본대 산책2

시간 제한 1초, 메모리 제한 512MB

# 조건

• 숭실 대학교 정보 과학관은 유배를 당해서 캠퍼스의 길 건너편에 있다.
• 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다.
• 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 꽃 이 활짝 핀 본 대를 선망한다.
• 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

• 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다.
• 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다.
• 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.)
• 이때 가능한 경로의 경우의 수를 구해주자.

입력

• D가 주어진다 (1 <=D <= 1,000,000,000)

출력

• 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

# 접근 방법

• 입력이 10억이 되므로 O(logN)의 복잡도로 해결하여야 한다. -> 분할정복 사용
• route 함수를 정의해준다.
  • 거리가 d, fr을 시작점으로 to를 끝점으로 하는 함수
  • 정보관에서 출발하여 다시 돌아와야 하므로 최초 호출은 (D, 0, 0)으로 해준다.
  • D를 절반의 경로 2개로 쪼개주며, 0에서 K로, K에서 0으로 경로들의 곱들의 합을 구해주면 된다.
  • 이 때, 중복되는 함수의 호출을 줄이기 위하여 메모이제이션을 사용해준다.
• 우선 출발 지점이자 도착지점인 정보과학관을 0번 인덱스로 반시계방향으로 인덱스를 +1로 사용해준다.
• 해당 인덱스에 연결되어 있는 건물들을 1로 표시해준다.
  • 아래 예시의 경우 1초만에 갈 수 있는 건물들을 표시해준 것이다.

campus = {}  
campus[1] = [  
    [0, 1, 0, 0, 0, 0, 0, 1],  
    [1, 0, 1, 0, 0, 0, 0, 1],  
    [0, 1, 0, 1, 0, 0, 1, 1],  
    [0, 0, 1, 0, 1, 0, 1, 0],  
    [0, 0, 0, 1, 0, 1, 0, 0],  
    [0, 0, 0, 0, 1, 0, 1, 0],  
    [0, 0, 1, 1, 0, 1, 0, 1],  
    [1, 1, 1, 0, 0, 0, 1, 0],  
]

• 즉 campus[d][fr][to] 가 존재한다면 반환해주고 없다면 8 * 8 배열을 할당해준다.
  • 예시를 들자면, 2초만에 정보관으로 오는 경로는
  • 1초만에 정보관과 연결되어있는 곳에서 정보관으로 가는 경우의 수와 같다.
  • 즉, 최초 d = 1 의 배열을 한 번 제곱해주면, 2초만에 갈 수 있는 경로의 수, 한 번 더 해준다면 3초만에 갈 수 있는 경로의 수가 적혀있으므로,
  • 분할 정복을 이용하여 제곱의 수를 줄여주고, 메모이제이션을 통하여 경로의 수를 구해주면 된다.
• 인접 행렬의 곱을 이용해주어야 하는 문제였다. 생각보다 어려워서 인접행렬의 곱에 대한 자료를 참고하고 풀 수 있었다.

https://driip.me/00556a4c-0782-4c5b-a86a-8e27e5f4ac1b

MOD = 1000000007  

def f(d, frm, to):  
    if d <= 1:  
        return campus[d][frm][to]  

    campus.setdefault(d, [[0 for _ in range(N)] for _ in range(N)])  
    if campus[d][frm][to]:  
        return campus[d][frm][to]  

    half = d // 2  
    other = half + 1 if d % 2 else half # 홀수면 +1    # half <= other  
    for k in range(N):  
        campus[d][frm][to] += f(half, frm, k) * f(other, k, to)  
        campus[d][frm][to] %= MOD  
    return campus[d][frm][to]  

N = 8  
campus = {}  
D = int(input())  

campus[1] = [  
    [0, 1, 0, 0, 0, 0, 0, 1],  
    [1, 0, 1, 0, 0, 0, 0, 1],  
    [0, 1, 0, 1, 0, 0, 1, 1],  
    [0, 0, 1, 0, 1, 0, 1, 0],  
    [0, 0, 0, 1, 0, 1, 0, 0],  
    [0, 0, 0, 0, 1, 0, 1, 0],  
    [0, 0, 1, 1, 0, 1, 0, 1],  
    [1, 1, 1, 0, 0, 0, 1, 0],  
]  





print(f(D, 0, 0))