백준 17401번
오늘 풀어본 문제는 백준의 17401번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
사람의 세포 수, 약 $37$ 조 개. 세포들은 몸 속에서 오늘도 열심히 일하고 있다. 그중에서도 우리의 적혈구는 혈관을 타고 돌아다니며 산소와 영양소를 운반해주는 중요한 역할을 맡고있다.
적혈구는 심장이나 폐 같은 거점들을 돌아다니면서 산소와 영양분을 운반한다. 몸 속에는 총 $N$ 개의 거점이 있고, 몇몇 거점은 통로를 통해 서로 이어져 있다. 거점 사이의 통로를 통과하는데는 $1$ 초가 걸린다. 하지만 혈관의 곳곳에는 판막이나 공사중인 부분들이 있기 때문에 매 초 거점 사이의 연결관계가 바뀐다. 그럼에도 불구하고 몸의 곳곳이 산소와 영양분을 필요로 하므로 적혈구는 가만히 있을 수 없으며, 매 초 통로를 무조건 하나 타야 한다. 일부 통로는 출발 거점과 도착 거점이 같을 수도 있다. 일부 거점의 특정 순간에는 나가는 통로가 없을 수도 있는데, 이 때는 도착한지 $1$ 초 후에 파괴되어 몸과 다시 하나가 된다. 잔혹하지만 우리의 몸은 이렇게 돌아간다.
우리의 적혈구는 매 순간 변하는 몸속 혈관 지도에 길을 헤매지만 그래도 최선을 다해서 하루하루 열심히 일을 하고 있다. 옆에 있던 백혈구가 길을 헤매는 적혈구를 보고 도와주고 싶다는 생각을 했다.
수십 시간의 유주 경험을 통해 백혈구는 몸속 혈관 지도가 $T$ 초를 주기로 반복된다는 것을 알게 되었다. 이 사실을 정리해서 적혈구가 거점 $A$ 에서 출발하여 정확히 $D$ 초 후 거점 $B$ 에 도달하게 되는 경우의 수를 모든 거점의 순서쌍에 대해 구해주고자 하지만 너무나도 단세포이기 때문에 머리가 나빠서 계산을 하지 못했다. 한 경로는, $D$ 초 동안 통과한 통로의 순열로 정의된다. 백혈구를 도와서 적혈구가 $D$ 초 동안 한 거점에서 다른 거점까지 움직일 수 있는 경우의 수를 구해주자!
입력
첫 번째 줄에는 백혈구가 알아낸 혈관 지도들의 주기인 자연수 T 와 거점의 개수인 자연수 N, 적혈구가 움직이는 시간인 정수 D 가 공백으로 구분되어 주어진다. $(1 \le T \le 100,\ 2 \le N \le 20, 0 \le D \le 109)$
그 뒤 거점 사이의 연결 관계를 나타내는 혈관 지도 $T$ 개가 순서대로 $1$ 번부터 $T$ 번까지 주어지는데, 혈관 지도가 주어지는 형식은 다음과 같다.
-
첫 번째 줄에는 거점 사이를 잇는 혈관의 개수인 자연수 $M_i$ 가 주어진다. $(0 \le Mi \le N2)$
-
그 뒤 $M_i$ 개의 줄에 걸쳐 세 자연수 $a,\ b,\ c$ 가 공백으로 구분되어 주어진다. 이는 거점 $a$ 에서 거점 $b$ 로 가는 서로 다른 단방향 통로가 $c$ 개 있음을 의미한다. $(1 \le a, b \le N, 1 \le c \le 1000)$
-
매 혈관 지도에 중복된 연결 관계는 주어지지 않는다.
$i4 초에서 $(i+1)$ 초 동안 이동할 때는 $(i % T + 1)$ 번 혈관 지도가 적용된다. $i % T$ 는 $i$ 를 $T$ 로 나눈 나머지를 의미한다.
출력
출력은 $N$ 개의 줄로 구성되며, $i$ 번째 줄에는 $N$ 개의 정수 $x_{i1},\ x_{i2}, \cdots, $x_{iN}$ 를 공백으로 구분하여 출력해야 한다. $x_{ij}$ 는 $0$ 초 때 거점 $i$ 에서 출발하여 정확히 $D$ 초 때 거점 $j$ 에 위치하게 되는 경로의 수를 $1,000,000,007$ 로 나눈 나머지이다.
풀이과정
1번째 시도
특정 지점에서 다른 지점으로 이동 가능한 경우의 수를 구하는 문제를 보고, 행렬의 거듭제곱을 이용해야 한다는 것을 알 수 있었다. 이런 유형의 다른 문제들과 차별되는 부분은, 혈관 지도가 주기를 가지고 바뀐다는 것인데, 이건 그냥 한 주기 내의 모든 행렬들을 미리 곱해놓고 그걸 거듭제곱 한 뒤, 한 주기가 되지 않는 남은 시간 만큼 행렬들을 곱하면 될 것이라고 생각하였다.
코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.
matrix.hpp
#ifndef __MATRIX_HPP__
#define __MATRIX_HPP__
#include <utility>
template <typename T>
class Matrix {
private:
size_t row;
size_t column;
T mod;
T** elements;
void clearElements(void) {
for (size_t i = 0; i < row; i++) {
delete[] elements[i];
}
delete[] elements;
}
public:
Matrix() : row(0), column(0), mod(0), elements(nullptr) {}
Matrix(size_t row, size_t column, bool identity = false, T mod = 0) : row(row), column(column), mod(mod) {
elements = new T * [row];
for (size_t i = 0; i < row; i++) {
elements[i] = new T[column];
for (size_t j = 0; j < column; j++) {
elements[i][j] = identity ? (i == j ? 1 : 0) : 0;
}
}
}
Matrix(const Matrix& other) : mod(other.mod) {
this->row = other.row;
this->column = other.column;
elements = new T * [row];
for (size_t i = 0; i < row; i++) {
elements[i] = new T[column];
for (size_t j = 0; j < column; j++) {
elements[i][j] = other.elements[i][j];
}
}
}
~Matrix() {
clearElements();
}
T* operator[] (size_t idx) {
return elements[idx];
}
const T* operator[] (size_t idx) const {
return elements[idx];
}
Matrix& operator= (const Matrix& other) {
if (this == &other) {
return *this;
}
clearElements();
this->row = other.row;
this->column = other.column;
elements = new T * [row];
for (size_t i = 0; i < row; i++) {
elements[i] = new T[column];
for (size_t j = 0; j < column; j++) {
elements[i][j] = other.elements[i][j];
}
}
return *this;
}
Matrix operator+ (const Matrix& other) {
Matrix result(*this);
for (size_t i = 0; i < row; i++) {
for (size_t j = 0; j < column; j++) {
result.elements[i][j] += other.elements[i][j];
if (mod != 0) {
result.elements[i][j] %= mod;
}
}
}
return result;
}
Matrix& operator+= (const Matrix& other) {
for (size_t i = 0; i < row; i++) {
for (size_t j = 0; j < column; j++) {
elements[i][j] += other.elements[i][j];
if (mod != 0) {
elements[i][j] %= mod;
}
}
}
return *this;
}
Matrix operator- (const Matrix& other) {
Matrix result(*this);
for (size_t i = 0; i < row; i++) {
for (size_t j = 0; j < column; j++) {
result.elements[i][j] -= other.elements[i][j];
if (mod != 0) {
result.elements[i][j] %= mod;
}
}
}
return result;
}
Matrix& operator-= (const Matrix& other) {
for (size_t i = 0; i < row; i++) {
for (size_t j = 0; j < column; j++) {
elements[i][j] -= other.elements[i][j];
if (mod != 0) {
elements[i][j] %= mod;
}
}
}
return *this;
}
Matrix operator* (const Matrix& other) {
Matrix result(this->row, other.column);
for (size_t i = 0; i < result.row; i++) {
for (size_t j = 0; j < result.column; j++) {
result.elements[i][j] = 0;
for (size_t k = 0; k < this->column; k++) {
T product = this->elements[i][k] * other.elements[k][j];
if (mod != 0) {
product %= mod;
}
result.elements[i][j] += product;
if (mod != 0) {
result.elements[i][j] %= mod;
}
}
}
}
return result;
}
Matrix power(size_t exponent) {
Matrix base(*this);
Matrix result(row, column, true, mod);
while (exponent > 0) {
if (exponent % 2 == 1) {
result = result * base;
}
exponent = exponent / 2;
base = base * base;
}
return result;
}
T trace(void) {
T result = 0;
for (size_t i = 0; i < row; i++) {
result += elements[i][i];
}
return result;
}
T determinant(void) { // WIP
return 0;
}
Matrix transpose(void) {
Matrix result(column, row);
for (size_t i = 0; i < row; i++) {
for (size_t j = 0; j < column; j++) {
result.elements[j][i] = elements[i][j];
}
}
return result;
}
const std::pair<size_t, size_t> size(void) const {
return std::make_pair(row, column);
}
friend std::ostream& operator<<(std::ostream& os, const Matrix matrix) {
for (size_t i = 0; i < matrix.row; i++) {
for (size_t j = 0; j < matrix.column; j++) {
os << matrix.elements[i][j] << ' ';
}
os << '\n';
}
return os;
}
};
#endif // __MATRIX_HPP__
main.hpp
#include <bits/extc++.h>
#include "matrix.hpp"
using namespace __gnu_pbds;
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll T, N, D, mod = 1'000'000'007;
cin >> T >> N >> D;
Matrix<ll> combined(N, N, false, mod);
Matrix<ll> rest(N, N, true, mod);
for (ll i=0; i<T; i++) {
ll M;
cin >> M;
Matrix<ll> curr(N, N, false, mod);
for (ll j=0; j<M; j++) {
ll a, b, c;
cin >> a >> b >> c;
a--;
b--;
curr[a][b] = c % mod;
}
if (D % T > i) {
rest = rest * curr;
}
else {
if (D % T == i) {
combined = rest;
}
combined = combined * curr;
}
}
cout << combined.power(D / T) * rest;
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
요즘들어 행렬을 이용한 문제를 푸는 건 즐거운 것 같다. 최근에 수학과 졸업시험 때문에 선형대수학을 복습해서 그런 것일까? 아쉬운 점은 아직까지 CLASS 문제에서 선형대수학을 이용하는 문제가 거의 없다는 것이다! 물론 다른 태그들과 비교해서 알고리즘에 있어 그 중요도가 다소 떨어지기 때문이라는 걸 알지만, 그래도 아쉬운건 어쩔 수 없는 것 같다…
그리고 이 문제를 풀어내면서 CLASS 6을 달성하게 되었다!
군대 오고 나서 분명 문제는 엄청 많이 푼 것 같은데, CLASS 6 도달하기까지 시간이 꽤나 걸린 것 같다. 게다가 군생활 목표중 하나인 CLASS 6, 7 모두 풀기를 이뤄내기 위해선, 앞으로 CLASS 문제를 5일에 1문제는 풀어야 한다는 무시무시한 결론이 나왔다! 조금 빨리빨리 문제를 풀 필요가 있을 것 같다.
그래서 앞으로는 랜덤 마라톤 문제 풀이를 줄이고, CLASS 문제 풀이에 집중하기로 했다. 어짜피 최근 다녀온 신병위로외박 때 노느라 마라톤 다 풀던 기록이 깨지기도 했고, 수학과 졸업 시험 공부도 해야하기 때문에 이런 결정을 내리게 되었다. 마라톤 문제들은 여력이 될 때 할만한 문제들 위주로 풀어보는 걸로 하겠다.
내가 만든 행렬 자료구조는 내 레포지토리2에서 확인할 수 있다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/17401
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/matrix.hpp