백준 11767번: Squawk Virus

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

11767번: Squawk Virus

---

왜 분할정복을 써야 하는 지 잘 모르겠습니다. $\left( T<10 \right)$

 

다른 사람들 코드를 보니까 주어진 인접행렬을 $T$ 제곱하여 $S^{th}$ row의 원소의 합을 구하면 되는 것 같습니다?

 

그 이전에 제 풀이를 먼저 소개하겠습니다.

 

제 풀이는, $T\geq 1$ 에서 $A_{ij}$ 에 대해 다음의 의미를 부여하는 것입니다.

 

$A_{ij}\;$ : $\;i$ 가 $j$ 에게 줄 수 있는 squawk 의 수

 

이때 $T=K$ 시점의 행렬을 $A\left( K \right)$ 로 나타내겠습니다.

 

그러면 $A\left( K \right)$ 에서 $A\left( K+1 \right)$ 로 전이하는 프로세스는 다음과 같습니다.

 

$\left( 1 \right)$ $i^{th}$ row에 곱해줄 계수 $C_{i}$ 를 구한다.

$\left( 2 \right)$ 이때 $C_{i}$ 의 값은 $A\left( K \right)$ 의 $i^{th}$ column 의 entries의 합으로 한다.

$\left( 3 \right)$ 모든 $0\leq i<N$ 에 대해 1~2를 반복한다.

 

예제 1로 보여드리겠습니다. 예제 1의 그래프는 다음과 같습니다.

 

 

위 프로세스가 $T\geq 1$ 에서 적용됨을 유념해주세요.

 

$\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 0 & 0 & 0 \\ 2 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 0 & 0 & 0 & 0 \\ 5 & 0 & 5 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 \end{bmatrix}$

 

가장 왼쪽이 $A\left( 1 \right)$ , 가장 오른쪽이 $A\left( 4 \right)$ 입니다.

 

문제에서 요구하는 건 결국 $T$ 시점에 전이되는 squawk의 수이므로,

 

이 풀이에서 정답은 $A\left( T-1 \right)$ 의 non-zero entries 의 합입니다.

 

예제 1에서는 $A\left( 3 \right)$ 이니까 $2+3+3=8$ 이겠군요. 실제로 정답입니다.

 

이 풀이를 구현한 제 코드는 다음과 같습니다.

#include <stdio.h>

typedef struct {
	long long array[100][100];
} Matrix;

int main() {

	int N, M, S, T;
	scanf("%d %d %d %d", &N, &M, &S, &T);

	Matrix Adjacent = { {{0}} };	
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		Adjacent.array[a][b] = 1;
		Adjacent.array[b][a] = 1;
	}
	
	if (T == 1) {
		long long answer = 0;
		for (int i = 0; i < N; i++) {
			answer += Adjacent.array[S][i];
		}
		printf("%lld", answer);
		return 0;
	}
	
	Matrix Result = { {{0}} };
	for (int i = 0; i < N; i++) {
		long long coef = Adjacent.array[S][i];
		for (int j = 0; j < N; j++) {
			Result.array[i][j] = coef * Adjacent.array[i][j];
		}
	}
	
	long long coef[100] = {0};
	while(T > 2) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				coef[i] += Result.array[j][i];
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				Result.array[i][j] = coef[i] * Adjacent.array[i][j];
			}
			coef[i] = 0;
		}
		T--;
	}
	
	long long answer = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			answer += Result.array[i][j];
		}
	}
	printf("%lld", answer);
	return 0;
}

(C11, 1156KB, 0ms, 제출번호 31039486)

---

이 풀이를 겨우 생각했는데, 정작 다른 분들은 인접행렬을 $T$ 제곱하여 푸셨더군요.

 

사실 $T<10$ 인 문제여서 굳이 안 그랬어도 괜찮지만, $T\leq 10^{9}$ 정도였으면 얘기가 꽤 달랐겠죠?

 

그런 면에서 의미가 있는 풀이라고 생각합니다.

 

지문을 잘 뜯어보면 squawk 바이러스의 움직임은 결국 우리가 각 정점을 이동하는 것과 똑같습니다.

 

제 풀이의 $C_{i}$ 값은 결국 정점 $i$ 로 도착하는 방법의 수인데요,

이걸 $i^{th}$ row 에 곱하면 나오는 것은 정점 $i$ 로 도착하여 다른 정점으로 가는 방법의 수이겠죠.

 

그래서 인접행렬을 $T$ 제곱하게 되면 이 문제의 해답이 될 수 있습니다.

 

이런 방식으로 접근한 제 코드는 다음과 같습니다.

#include <stdio.h>

typedef struct {
	long long array[100][100];
} Matrix;

Matrix matrix_multiply (Matrix A, Matrix B, int size);
Matrix matrix_power (Matrix A, int size, int power);

int main() {

	int N, M, S, T;
	scanf("%d %d %d %d", &N, &M, &S, &T);

	Matrix Adjacent = { {{0}} };	
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		Adjacent.array[a][b] = 1;
		Adjacent.array[b][a] = 1;
	}
    Matrix Result = matrix_power(Adjacent, N, T);
	
	long long answer = 0;
	for (int i = 0; i < N; i++) {
	    answer += Result.array[S][i];
	}
	printf("%lld", answer);
	return 0;
}

Matrix matrix_multiply (Matrix A, Matrix B, int size) {
    Matrix Result =  { {{0}} };
    for (int i = 0; i < size; i++) {
        for (int k = 0; k < size; k++) {
            for (int j = 0; j < size; j++) {
                Result.array[i][j] += A.array[i][k] * B.array[k][j];
            }
        }
    }
    return Result;
}

Matrix matrix_power (Matrix A, int size, int power) {
    Matrix Result = { {{0}} };
    for (int i = 0; i < size; i++) {
        Result.array[i][i] = 1;
    }
    while (power) {
        if (power % 2) {
            Result = matrix_multiply(Result, A, size);
        }
        A = matrix_multiply(A, A, size);
        power /= 2;
    }
    return Result;
}

(C11, 1620KB, 4ms, 제출번호 31693354)

---

그런데 딱히 비싼 연산을 쓴 것 같진 않은데도 시간이랑 메모리가 더 커졌습니다.

 

결국 $T<10$ 에서는 제 풀이가 더 나았던 건지, 아니면 후자의 풀이를 제대로 최적화하지 못했던 건지...