백준 1533번: 길의 개수 (Graph, Matrix)

문제링크:1533번: 길의 개수 (acmicpc.net)

1533번: 길의 개수

이 문제는 노드와 간선들이 인접행렬로 주어졌을 때, 시작노드로부터 도착 노드까지의 경로 중 시간이 T와 정확히 일치하는 경로들의 개수를 구하는 문제이다.

 

먼저 기존에 가중치가 없는 간선들이 인접행렬로 주어졌을 때에, 행렬의 곱을 이용해 경로의 개수를 구할 수 있었다.

만약 0,1,2의 노드와 가중치가 없는 간선들이 인접행렬로 다음과 같이 주어지면 각 matrix[i][j]는 i에서 j로 가는 경로가 있으면 1, 없으면 0이다.

[0 1 0]

[1 0 0]

[1 1 0]

만약 이 행렬을 제곱한다면 

matrixsqr[0][0]= (matrix생략) [0][0]*[0][0] + [0][1]*[1][0] + [0][2]*[2][0] 로 표현된다.

잘 살펴보면 앞부터 (0에서0) * (0에서0) + (0에서1) * (1에서0) + (0에서2) * (2에서0) 으로 결과값은 간선 2개를 거쳐 [0]에서 출발하여 [0]으로 돌아오는 경우의 수 합이 저장되게 된다.

일반화하면 matrix의 K제곱을 할 시 각 [i][j] 에는 간선 K개를 거쳐 노드 [i]에서 [j]로 돌아오는 경우의 수 합이 저장되게 된다.

 

나는 혼자 해결해 보려 했지만 생각 할 수 없어 검색을 통해 답을 구할 수 있었다.

이 문제의 A[i][j]<=5 라는 조건 하에 가중치는 모두 5보다 작거나 같다는 것을 알 수 있다. 그래서 각 노드를 5개로 쪼개 준다.

 

기존의 1이라는 노드는 (1-0), (1-1), (1-2), (1-3), (1-4) 이렇게 5개가 되었다고 생각한다. 그리고 주어진 가중치를 고려 해 1분 뒤를 생각한다. 예를 들어 0->1로 5분이 걸린다면, (A[0][1]=5) 1분 뒤에는 4분 더 가야 도달하므로 (1-4)에 위치하고, 또 1분 뒤에는 (1-3), 1분 뒤 (1-2), 1분 뒤 (1-1), 1분 뒤(1-0)에 위치하게 된다. 이렇게 하면 (0-0)에서 (1-0)까지 도달하는데 5분이 걸렸음을 표현 할 수 있다.

 

(1-0)을 진짜 노드1 이라 생각하고 (1-n)뒤의 n은 앞으로 n번 더 가야 진짜 노드 1에 도착할 수 있다고 생각하면 이해가 쉬웠다. 그렇다면 기존의 A[0][1]=5를 아까 확장된 노드로 표현하면 A[(0-0)][(1-4)]=1 이라고 표현 할 수 있다. 출발 노드는 무조건 진짜 노드에서 출발해야 하므로 출발 노드는 (N-0)이다.

 

이렇게 하면 5배로 확장된 행렬에 가중치를 모두 1로 표현할 수 있고, 가중치가 모두 1이라면 위에서 설명한 길이 있는 경우는 1, 없는 경우는 0으로 표현된 행렬을 (T)제곱하여 경우의 수 합을 구할 수 있다.

 

실제 matrix를 만들 때에는 (0-0) (0-1)이렇게 만들 수 없으니 총 (5*N)X(5*N) 행렬을 만들어 0,1,2,3,4 = (0-0) (0-1) (0-2) (0-3) (0-4)로 생각한다.

import sys

N,S,E,T=map(int,sys.stdin.readline().rstrip().split())

MOD=1000003

matrix=[[0 for _ in range(5*N)] for _ in range(5*N)]


for i in range(N):
    row=list(sys.stdin.readline().rstrip())
    for j in range(N):
        if int(row[j])>0:
            matrix[5*i][5*j+(int(row[j])-1)]=1

for i in range(5*N):
    for j in range(5*N):
        if (i//5)==(j//5):
            if (i%5)-(j%5)==1:
                matrix[i][j]=1

def matpower(mat,n):
    if n==1:
        return mat
    else:
        if n%2==0:
            matsqr=matmult(mat,mat)
            return matpower(matsqr,n//2)
        elif n%2==1:
            return matmult(matpower(mat,n-1),mat)

def matmult(mat1,mat2):
    multmat=[[0 for _ in range(5*N)] for _ in range(5*N)]
    for i in range(5*N):
        for j in range(5*N):
            val=0
            for k in range(5*N):
                A=mat1[i][k]
                B=mat2[k][j]
                val+=(A*B)%MOD
            multmat[i][j]=val%MOD
    return multmat

matp=matpower(matrix,T)
print(matp[5*(S-1)][5*(E-1)])

입력되는 인접 행렬을 위에 설명한 대로 확장하여 1,0으로 이루어진 행렬을 만들어 주고, 이제 각 노드 내에서 길을 만들어 줘야 한다. (0-5)->(0-4), (0-4)->(0-3),.. (0-1)->(0,0)과 같은 노드 내의 길들은 항상 성립하므로 N개의 노드 모두 (-다시) 사으이 간선들을 표현해 준다. i//5==j//5 는 같은 노드인 조건을 표현하고, i%5-j%5==1 은 (-다시)사이에서 큰 (-다시) 가 1보다 작은 (-다시)로 연결되는 조건을 표현한다.

 

분할 정복을 통해 행렬 제곱을 구현해주면 된다. 특이사항으로 S에서 E로 가는 답을 구할때 진짜 노드인 (S-0)과 (E-0)을 구해야 한다. 진짜 노드(S-0)에서 출발한 경우, 그리고 (E-1), (E-2), (E-3).. 는 생각해 보면 아직 E에 완전히 도달하지 못하고 아직 가는 길인 경우이다.