[백준] 1533. 길의 개수 (파이썬 / Python)

문제 출처 : https://www.acmicpc.net/problem/1533

1533번: 길의 개수

 

---

1. 문제 풀이

1.1. 인접행렬의 특징

본 문제는 인접행렬을 통해 구현하는 문제이다.

가령 다음과 같은 행렬이 있다고 가정해보자. matrix[i][j] 는 i번 노드에서 j번 노드로 갈 수 있는 경우의 수를 표현한 것이다.

matrix

만약 i번 노드에서 j번 노드로 한 개의 노드를 경유해서 가고 싶다고 가정해보자.i = 0, j = 1이라고 가정하겠다.

그럼 다음과 같은 경우의 수를 생각해 볼 수 있다.

0 -> 0 -> 1

0 -> 1 -> 1

0 -> 2 -> 1

 

즉, 0번 노드에서 1번 노드로 한 개의 노드를 경유해서 가는 경우는 다음과 같이 표현할 수 있다.

mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1] + mat[0][2] * mat[2][1]

그리고 해당 식은 다음과 같다.

mat^1[i][j]가 i에서 j로 바로 가는 경우의 수라는 것을 고려했을 때,

mat^2[i][j]는 j를 두 번째 목적지로 했을 때, i에서 갈 수 있는 경우의 수라는 점을 유추할 수 있다.

(참조 : https://www.acmicpc.net/board/view/13807)

 

그렇다면 다시 문제로 돌아가서, 문제의 입력값을 확인해보자.

여기서 mat[i][j]는 i에서 j로 가는 경우의 수가 아니라, i에서 j로 가는 데에 걸리는 시간임을 확인할 수 있다.

단순히 위와 같이 계산해 보았을 때, 두 번만에 0에서 1로 가는 데에 걸리는 시간은 4초가 아닐 뿐더러, 우리가 원하는 값은 걸리는 시간이 아니라 경우의 수기 때문에 위와 같은 방법으로 계산하면 안된다.

 

1.2. 인접행렬로의 변환

따라서 입력값을 우리가 원하는 형태로 변환하는 작업이 필요하다.

문제에 따르면, 한 노드에서 다른 노드로 갈 수 있는 데 걸리는 최대 시간은 5초라고 한다.

이 점에 착안하여, 각 셀의 위치 정보가 시간을 내포하며, 각 셀의 내용이 경우의 수를 의미하도록 행렬을 변환할 수 있다.

우선, 각 행과 열의 [1, 2, 3, 4, 5]는 시간을 나타낸다. 즉, 0번 노드의 3은, 0번 노드가 3초 후에 갈 수 있는 곳을 나타낸다. 그러나 위 설명은 직관적으로 이해하기 어려우므로, 그래프를 통해 설명하도록 한다.

각 화살표는 1초 후에 각 노드가 이동할 노드를 의미한다.

 

즉, "0-4 노드"는 2초 후에 "0-2 노드"로 이동할 수 있다.

"0-4 노드"는 1초 후에 "0-3 노드"로 이동하며, "0-3 노드"는 1초 후에 "0-2" 노드로 이동할 수 있기 때문이다.

 

그렇다면, "2번 노드가 0번 노드로 가는 데에 2초가 걸린다"라는 정보를 어떻게 표현할 수 있을까?

위와 같이 표현할 수 있다.

"2-1 노드"는 1초 후에 "0-2 노드"로 이동하며, 다시 1초가 지나면 "0-2 노드"는 "0-1 노드"로 이동하기 때문이다.

 

그렇다면 입력값을 원하는 형태로 변환하는 작업을 해보자.

우선 교차점의 개수가 3개이므로, 그래프로는 다음과 같이 표현할 수 있다.

이를 우리가 원하는 형태로 표현하면 다음과 같다.

이는 아직 어느 노드에서 다른 노드로 가는 데 걸리는 시간을 고려하지 않은 상태이다.

이제 입력값을 다시 확인하여 해당 행렬을 다시 갱신할 수 있도록 하자.

입력 값은 다음과 같이 해석할 수 있다.

 

1. 0번 노드에서 1번 노드로 가는 데 1초, 2번 노드로 가는 데 2초가 걸린다고 한다.

→ "0-1 노드"에서 "1-1 노드"로 갈 수 있다.

→ "0-1 노드"에서 "2-2 노드"로 갈 수 있다.

 

2. 1번 노드에서 0번 노드로 가는 데 2초, 2번 노드로 가는 데 1초가 걸린다고 한다.

→ "1-1 노드"에서 "0-2 노드"로 갈 수 있다.

→ "1-1 노드"에서 "2-1 노드"로 갈 수 있다.

 

3. 2번 노드에서 0번 노드로 가는 데 1초, 1번 노드로 가는 데 2초가 걸린다고 한다.

→ "2-1 노드"에서 "0-1 노드"로 갈 수 있다.

→ "2-1 노드"에서 "1-2 노드"로 갈 수 있다.

 

그리고 이를 행렬에 대입하면 다음과 같이 된다.

이제 앞서 언급한 것처럼, 해당 행렬을 n제곱 하는 것으로, n초 후에 특정 경로로 가는 경우의 수를 확인할 수 있다.

문제에서는 1번 교차로에서 3번 교차로까지 5초 동안 갈 수 있는 경우의 수를 구하고자 한다.

 

실제로 해당 행렬을 5제곱 하면 다음과 같은 행렬을 얻을 수 있다.

교차로는 1-index므로, 실질적으로는 "0-1번 노드"로부터 "2-1번 노드"까지의 경우의 수를 구해주면 된다.

따라서 정답은 8이다.

---

2. 코드

import sys
input = sys.stdin.readline
# sys.stdin = open("input.txt", "r")

num_roads, start_idx, end_idx, late_time = map(int, input().split())

# 가중지 없는 인접 행렬 만들기
mat = [[0]*5*num_roads for _ in range(5*num_roads)]

# 인접 행렬 초기화
for row_idx in range(1, 5*num_roads):
    if row_idx % 5:
        mat[row_idx][row_idx-1] = 1

# 입력값 받아서 인접행렬 초기화
for row_idx in range(num_roads):
    row = list(map(int, list(input().rstrip())))

    for col_idx, next_road in enumerate(row):
        if next_road:
            mat[row_idx*5][5*col_idx + next_road-1] = 1

# 관련 함수 정의
def inner_product(vec_a, vec_b):
    # 두 벡터의 내적
    answer = 0

    for idx in range(len(vec_a)):
        answer += vec_a[idx] * vec_b[idx] % 1000003

    return answer % 1000003

def mat_mul(mat_a, mat_b):
    # 두 행열의 곱
    result = []

    b_transposed = list(zip(*mat_b))

    for row_idx in range(len(mat_a)):
        row = []
        for col_idx in range(len(mat_b)):
            row.append(inner_product(mat_a[row_idx], b_transposed[col_idx]))
        result.append(row)
    
    return result

# 분할 정복을 이용한 거듭제곱
mat_dic = dict({1 : mat})

def mat_pow(exp):

    temp_mat = mat_dic.get(exp)

    if temp_mat:
        return temp_mat
    
    mid = exp//2
    left = mat_pow(mid)
    right = mat_pow(exp - mid)

    mat_dic[exp] = mat_mul(left, right)
    return mat_dic[exp]

result = mat_pow(late_time)
print(result[(start_idx-1) *5][(end_idx-1) *5])

---

3. 결과

---