백준 1533번
오늘 풀어본 문제는 백준의 1533번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
세준이는 정문이를 데리러 공항으로 가기로 했다. 하지만, 방금 세준이는 정문이의 비행기가 연착된다는 전화를 받았다. 세준이는 정문이가 정확하게 몇 분 늦는지 알고 있고, 그 시간 동안 밖에서 드라이브를 하려고 한다. 정문이가 늦는 시간을 $T$ 라고 하자.
세준이는 자기가 지금 있는 위치에서부터, 공항까지 정확하게 $T$ 분만에 도착하는 경로의 개수를 구하고 싶다.
길의 정보는 인접행렬로 주어진다. $A[i][j]$ 가 $0$ 이라면 $i$ 에서 $j$ 로 가는 길이 없는 것이고, $A[i][j] \le 5$ 라면, 정확히 그 만큼의 시간이 걸리는 $i$ 에서 $j$ 로 가는 길이 있는 것이다.
입력
첫째 줄에 교차점의 개수 $N$ 이 주어진다. $N$ 은 $10$ 보다 작거나 같고, 시작점의 위치 $S$ 와 끝점의 위치 $E$, 그리고 정문이가 늦는 시간 $T$ 도 주어진다. $S$ 와 $E$ 는 $N$ 보다 작거나 같은 자연수이다. $T$ 는 $1,000,000,000$ 보다 작거나 같은 자연수이다. 둘째 줄부터 길의 정보가 주어진다.
출력
첫째 줄에 경로의 개수를 $1,000,003$ 로 나눈 나머지를 출력한다.
풀이과정
1번째 시도
경로의 개수를 알아내야 한다는 점에서, 인접 행렬의 제곱을 이용하여 해결할 수 있을 것이라고 생각하였다.
행렬을 제곱하는 것은 분할정복을 이용하여 시간 내에 할 수 있어 문제가 되지 않았지만, 인접 행렬을 어떻게 구성해야 하는가가 문제가 되었다.
일반적인 경우와 달리 정점 사이를 이동할 때 시간이 걸리기 때문에 이를 어떻게 표현하는가가 관건이었는데, 아이디어가 결국 떠오르지 않아 다른 사람들이 해결한 방식을 찾아보았고, ‘정점 분할’ 이라는 기가막힌 아이디어를 발견하게 되었다.
모든 길을 가는데 걸리는 시간은 5이하 이기 때문에 한 개의 정점을 5개로 분할하여
- 원래 정점 <- 원래 정점까지 가기 위해 걸리는 시간이 1인 정점 <- 원래 정점까지 가기 위해 걸리는 시간이 2인 정점 <- … <- 원래 정점까지 가기 위해 걸리는 시간이 4인 정점
위와 같이 연결하고, 다른 정점에서 어떤 정점으로 가는데 걸리는 시간에 따라 5개의 정점 중 적절한 정점에 연결을 해주는 방식으로 인접 행렬를 구성할 수 있던 것이다!
코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.
matrix.hpp
#ifndef __MATRIX_HPP__
#define __MATRIX_HPP__
template <typename T>
class Matrix {
private:
size_t row;
size_t column;
T mod;
T** elements;
public:
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]{};
}
if (identity) {
for (int i=0; i<row; i++) {
elements[i][i] = static_cast<T>(1);
}
}
}
Matrix(const Matrix& other) : row(other.row), column(other.column), mod(other.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] = other.elements[i][j];
}
}
}
~Matrix() {
for (size_t i = 0; i < row; i++) {
delete[] elements[i];
}
delete[] elements;
}
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;
}
for (size_t i = 0; i < row; i++) {
delete[] elements[i];
}
delete[] elements;
row = other.row;
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->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;
}
const size_t getRow(void) const {
return row;
}
const size_t getColumn(void) const {
return column;
}
};
#endif // __MATRIX_HPP__
main.cpp
#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);
cout.tie(nullptr);
int N, S, E, T;
cin >> N >> S >> E >> T;
Matrix<int> matrix(5 * N, 5 * N, false, 1000003);
for (int i=0; i<N; i++) {
matrix[5 * i + 4][5 * i + 3] = 1;
matrix[5 * i + 3][5 * i + 2] = 1;
matrix[5 * i + 2][5 * i + 1] = 1;
matrix[5 * i + 1][5 * i + 0] = 1;
string input;
cin >> input;
for (int j=0; j<N; j++) {
int dist = input[j] - '0';
if (dist != 0) {
matrix[5 * i][5 * j - 1 + dist] = 1;
}
}
}
Matrix<int> result = matrix.power(T);
cout << result[5 * (S-1)][5 * (E-1)];
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
2번째 시도
기가 막힌 아이디어를 검색해서 알아내고도 문제를 해결하지 못해 질문 게시판을 찾아보다가, 오버플로우가 문제일 수 있다는 걸 알아내었다. 그래서 모든 정수형 변수들의 자료형을 int 대신 unsigned long long int 로 바꿔치기 하였다.
코드는 main.cpp 부분만 다음과 같이 수정하였다.
main.cpp
#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);
cout.tie(nullptr);
ull N, S, E, T;
cin >> N >> S >> E >> T;
Matrix<ull> matrix(5 * N, 5 * N, false, 1000003);
for (ull i=0; i<N; i++) {
matrix[5 * i + 4][5 * i + 3] = 1;
matrix[5 * i + 3][5 * i + 2] = 1;
matrix[5 * i + 2][5 * i + 1] = 1;
matrix[5 * i + 1][5 * i + 0] = 1;
string input;
cin >> input;
for (ull j=0; j<N; j++) {
ull dist = input[j] - '0';
if (dist != 0) {
matrix[5 * i][5 * j - 1 + dist] = 1;
}
}
}
Matrix<ull> result = matrix.power(T);
cout << result[5 * (S-1)][5 * (E-1)];
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
오늘 문제를 푸는데 사용된 아이디어는 무척 신선하고 충격적었다! 그래프 문제를 이것저것 풀어봤지만 정점을 쪼갠다는 생각은 한 번도 못해봤기 때문이다. 나중에는 이런 아이디어를 스스로 떠올릴 수 있게되면 좋겠다.
내가 만든 행렬 자료구조는 내 레포지토리2에서 확인할 수 있다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1533
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/matrix.hpp