백준 13380번: Found

https://www.acmicpc.net/problem/13380

13380번: Found

---

문제 지문을 읽어보면, $N$개의 intersection이 있고 $M$개의 road가 있고 $T$ 만큼 지난 후에 둘이 만납니다.

그래서 [BOJ12916]이나 [BOJ14289] 같이 $N \times N$ adjacency matrix를 만들고 $T$ 제곱하면 틀립니다.

 

그렇게 했을 때 틀리는 이유는, 13380번 문제의 경우 Also they do not want to meet each other before T minutes. 라고 하고 있기 때문입니다. 다시 말해 위에서 말한 나이브한 접근으로는 $T$ 전에 만나는 경우를 배제하지 못하기 때문입니다.

 

저는 이 부분에서 큰 어려움을 겪어서, 잠시 문제를 포기했다가 우연히 이 글을 접하고 AC를 받게 되었습니다.

https://koosaga.com/231

---

위 글에서 말하는 방법을 풀어쓰자면, 우선 순서쌍 $\left ( \textrm{Alice}, \textrm{Bob} \right )$을 현재 Alice와 Bob이 서있는 intersection의 번호로 정의합니다.

 

순서쌍의 개수는 $\left (1,1 \right )$부터 $\left ( N, N \right )$까지 $N \times N$ 입니다.

 

$M$개의 road는 여기서 각 순서쌍 간 상태전이가 일어날 수 있는지를 판가름해줍니다.

 

그렇게 $N^{2} \times N^{2}$ adjacency matrix를 구성하여 $T$ 제곱하면 $\cdots$ 틀립니다!

---

왜냐하면, 이렇게 해도 여전히 $T$ 시간 전에 만나는 경우를 배제하지 못했기 때문입니다.

 

저의 경우 이 부분을 해결하기 위해, $\left ( \textrm{Alice}, \textrm{Bob} \right ) = \left ( k,k \right )$인 경우, 더 이상 다른 순서쌍으로 전이하지 못하도록 matrix를 수정했습니다.

 

그렇게 하면 $T$ 전에 둘이 만나더라도 더 이상 다른 intersection으로 옮기지 못하여 전체 경우의 수에 반영이 되지 않을 거라 판단했고, 다행히 맞아떨어졌습니다.

 

원래는 adjacency matrix를 어떻게 모델링했는지 수식으로 설명하려 했는데, 괜히 복잡해지는 것 같아 말로 간략히 설명하겠습니다.

 

matrix의 0행은 다음과 같습니다.

 

$[0][0]$ : $\left( 1,1 \right )$에서 $\left( 1,1 \right )$ 으로 전이할 수 있다면 0, 전이할 수 없다면 1입니다.

$[0][1]$ : $\left( 1,1 \right )$에서 $\left( 1,2 \right )$ 으로 전이할 수 있다면 0, 전이할 수 없다면 1입니다.

$\vdots$

$[0][N-1]$ : $\left( 1,1 \right )$에서 $\left( 1,N \right )$ 으로 전이할 수 있다면 0, 전이할 수 없다면 1입니다.

$[0][N]$ : $\left( 1,1 \right )$에서 $\left( 2,1 \right )$ 으로 전이할 수 있다면 0, 전이할 수 없다면 1입니다.

$[0][N+1]$ : $\left( 1,1 \right )$에서 $\left( 2,2 \right )$ 으로 전이할 수 있다면 0, 전이할 수 없다면 1입니다.

$\vdots$

$[0][2N-1]$ : $\left( 1,1 \right )$에서 $\left( 2,N \right )$ 으로 전이할 수 있다면 0, 전이할 수 없다면 1입니다.

$\vdots$

$[0][N^{2}-1]$ : $\left( 1,1 \right )$에서 $\left( N,N \right )$ 으로 전이할 수 있다면 0, 전이할 수 없다면 1입니다.

 

이렇게 0행부터 $N^{2}-1$ 행까지 순서대로 구축해주면 됩니다. (물론, 앞서 말했던 대로 0행의 entries는 주어지는 road에 상관없이 0으로 고정됩니다.)

$M$개의 road를 통해 $N \times N$ adjacency matrix는 이미 만들어져 있을 것입니다. 그걸 활용하면 됩니다.

---

이렇게 adjacency matrix를 구했다면 $T$ 제곱하여, $\left( 1,N \right )$에서 $\left( k,k \right )$로 가는 방법의 수를 summation해주면 됩니다.

즉 최종적인 답은 다음과 같습니다.

$$ \textrm{Answer} = \sum_{k=1}^{N} \textrm{matrix} [N-1][(k-1) \times N + (k-1)] $$

---

이제 시간복잡도를 설명하겠습니다. $N^{2} \times N^{2}$ 크기 행렬의 $T$제곱을 $K$번 반복하고 있기 때문에,

 

전체 시간복잡도는 $O \left ( KN^{6} \log T \right )$ 이며 $N \leq 10$이므로 충분히 시간 안에 해결할 수 있는 범위입니다.

 

다음은 제 코드입니다.

#include <stdio.h>
#define mod 9973

typedef struct {
	unsigned long long array[100][100];
} Matrix;
 
Matrix matrix_multiply_modular (Matrix A, Matrix B, int size);
Matrix matrix_power_modular (Matrix A, int size, long long P);

int main(void) {
	
	int K;
	scanf("%d", &K);
	while(K--)
	{
		int N, M; long long T;
		scanf("%d %d %lld", &N, &M, &T);
		
		int map[11][11] = {{}};
		while(M--)
		{
			int A, B;
			scanf("%d %d", &A, &B);
			map[A][B] = map[B][A] = 1;
		}
		
		Matrix Base = {{{}}};
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i == j) continue;
				for (int k = 0; k < N; k++) {
                    if (i == k) continue;
					for (int l = 0; l < N; l++) {
						if (j == l) continue;
						Base.array[i*N+j][k*N+l] = map[i+1][k+1] & map[j+1][l+1];
					}
				}
			}
		}
		Base = matrix_power_modular(Base, N*N, T);
		
		long long answer = 0;
		for (int k = 0; k < N; k++) {
			answer = (answer + Base.array[N-1][k*N+k]) % mod;
		}
		printf("%lld\n", answer);
	}
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
	Matrix result = {{{}}};
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			for (int k = 0; k < size; k++) {
				result.array[i][j] += A.array[i][k] * B.array[k][j];
			}
            result.array[i][j] %= mod;
		}
	}
	return result;
}
 
Matrix matrix_power_modular (Matrix A, int size, long long P) {
	Matrix result = {{{}}};
	for (int i = 0; i < size; i++) {
		result.array[i][i] = 1;
	}
	while(P) {
		if (P % 2) {
			result = matrix_multiply_modular (result, A, size);
		}
		A = matrix_multiply_modular (A, A, size);
		P /= 2;
	}
	return result;
}

(C11, 120ms, 1616KB, 제출번호 54211556)

---

처음 봤을 땐 정말 쉽게 풀 수 있을 것만 같았는데, 너무 오래 걸렸습니다...