백준 2099번: The game of death

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

2099번: The game of death

---

The game of death 라는 술게임이 있죠.

 

제가 했을 때는 그냥 각자 한 사람씩만 가리켰던 것 같은데, 지역에 따라 룰이 다른 건지...

 

아무튼, 이 문제의 상황은, 한 사람이 두 팔로 누군가를 가리키고 있는 상황입니다.

 

이 문제를 해결하기 위해 인접행렬을 만듭니다.

 

그 인접행렬을 $K$ 제곱하면 문제에서 원하는 답이 나옵니다!

 

그런데 이 문제에서는 특별히 $\cdots$ 경로의 존재 여부 를 묻고 있기 때문에, bool 행렬로 나타내겠습니다.

 

경로가 존재하면 true, 존재하지 않으면 false 이겠죠?

 

평소에 제가 사용하는 행렬곱 함수의 형태는 다음과 같습니다.

 

$res\left[ i \right]\left[ j \right]=res\left[ i \right]\left[ j \right]+A\left[ i \right]\left[ k \right]\ast B\left[ k \right]\left[ j \right]$

 

우리가 bool 변수를 다루고 있으니까

 

곱셈을 Logical AND 연산, 덧셈을 Logical OR 연산으로 해결할 수 있습니다.

 

또한 i-k-j 순으로 배치한 3중 for loop에서, 가장 안의 loop으로 들어가는 횟수를 줄이기 위해

 

k-loop 에서 $A\left[ i \right]\left[ k \right]$ 의 true/false 에 따라 분기하도록 했습니다.

 

제 코드는 다음과 같습니다.

#include <stdio.h>
#include <stdbool.h>

typedef struct {
	bool array[200][200];
} Matrix;

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

int main() {
	
	int N, K, M;
	scanf("%d %d %d", &N, &K, &M);
	
	Matrix Base = { {{0}} };
	for (int i = 0; i < N; i++) {
		int a, b;
        scanf("%d %d", &a, &b);
		Base.array[i][a-1] = Base.array[i][b-1] = true;
	}
	Base = matrix_power (Base, N, K);

	while(M--) {
		int a, b;
        scanf("%d %d", &a, &b);
		if (Base.array[a-1][b-1]) {
			printf("death\n");
		}
		else {
			printf("life\n");
		}
	}
	
	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++) {
			if (A.array[i][k]) {
			    for (int j = 0; j < size; j++) {
				    result.array[i][j] |= B.array[k][j];
			    }
			}
		}
	}
	return result;
}

Matrix matrix_power (Matrix Base, 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, Base, size);
		}
		Base = matrix_multiply (Base, Base, size);
		power /= 2;
	}
	return result;
}

(C11, 1308KB, 468ms, 제출번호 31678776)

---

이 코드에서, 사실 468ms 에서 만족해도 됐을 텐데, 저는 다음 링크의 fast IO 함수를 적용해보기로 했습니다.

( https://panty.run/fastio/ )

 

그 결과는 다음과 같습니다.

#include <stdio.h>
#include <stdbool.h>

typedef struct {
	bool array[200][200];
} Matrix;

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

char buf[1 << 17];

char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}

int readInt() {
    int ret = 0;
    char now = read();
    
    while (now == 10 || now == 32) now = read();
    while (now >= 48 && now <= 57) {
        ret = ret * 10 + now - 48;
        now = read();
    }
    return ret;
}

int main() {
	
	int N, K, M;
	scanf("%d %d %d", &N, &K, &M);
	
	Matrix Base = { {{0}} };
	for (int i = 0; i < N; i++) {
		int a = readInt(), b = readInt();
		Base.array[i][a-1] = Base.array[i][b-1] = true;
	}
	Base = matrix_power (Base, N, K);

	while(M--) {
		int a = readInt(), b = readInt();
		if (Base.array[a-1][b-1]) {
			printf("death\n");
		}
		else {
			printf("life\n");
		}
	}
	
	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++) {
			if (A.array[i][k]) {
			    for (int j = 0; j < size; j++) {
				    result.array[i][j] |= B.array[k][j];
			    }
			}
		}
	}
	return result;
}

Matrix matrix_power (Matrix Base, 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, Base, size);
		}
		Base = matrix_multiply (Base, Base, size);
		power /= 2;
	}
	return result;
}

(C11, 1436KB, 252ms, 제출번호 31678699)

---

확실히, $10^{6}$ 개를 인풋 받아야 하는 상황이라 적용한 보람이 있었습니다.

 

fast IO 없이 200ms 대를 뚫은 분은, memset과 memcpy를 쓰셨더군요.

 

또 행렬을 구조체에 담지 않고 전역변수로 선언해서 사용하는 모습이 인상적이었습니다.

 

저 나름대로 그 방법을 따라해보려 했는데, 익숙하지 않은 방법이라 그런지 더 나은 결과가 나오지 않았어요.

 

그래서 그 코드는 여기에 올리지는 않겠습니다.