문제 설명
문제 풀이
- 지목된 상태 그래프를 인접행렬 형태로 나타내고 행렬의 거듭제곱을 사용해서 풀이하였다.
- 우선 K <= 100만 이므로, 최대 19승까지 인접행렬 거듭제곱 값을 저장해놓는다.
- K를 이진법 변환방식을 통해 해당 행렬들을 곱해주면 K번 진행했을 때 최종 인접행렬이 나온다.
- 해당 인접행렬을 참고하여 결과 출력
소스 코드 (JAVA)
import java.io.*;
import java.util.*;
class Main {
static BufferedWriter bw;
static BufferedReader br;
static class Pair {
int a, b;
public Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
static int N, K, M;
static boolean[][][] adj;
static Pair[] probs;
static void makeAdj() {
for (int ind = 1; ind < 20; ind++) {
if (Math.pow(2, ind) > K) break;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
boolean res = false;
for (int k = 0; k < N; k++) {
if (adj[ind-1][i][k] && adj[ind-1][k][j]) {
res = true;
break;
}
}
adj[ind][i][j] = res;
}
}
}
}
static boolean[][] multAdj(boolean[][] a, boolean[][] b) {
boolean[][] res = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
boolean tmpRes = false;
for (int k = 0; k < N; k++) {
if (a[i][k] && b[k][j]) {
tmpRes = true;
break;
}
}
res[i][j] = tmpRes;
}
}
return res;
}
static void solve() throws IOException {
makeAdj();
int cur = K;
int ind = 0;
boolean[][] result = null;
while(cur != 0) {
if (cur % 2 == 1) {
if (result == null) {
result = adj[ind].clone();
}
else {
result = multAdj(result, adj[ind]);
}
}
cur /= 2;
ind++;
}
for (int i = 0; i < M; i++) {
if (result[probs[i].a][probs[i].b]) bw.write("death\n");
else bw.write("life\n");
}
bw.flush();
}
static void input() throws IOException {
bw = new BufferedWriter(new OutputStreamWriter(System.out));
br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
adj = new boolean[20][N][N];
probs = new Pair[M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
adj[0][i][Integer.parseInt(st.nextToken()) - 1] = true;
adj[0][i][Integer.parseInt(st.nextToken()) - 1] = true;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
probs[i] = new Pair(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
}
}
public static void main(String[] args) throws IOException {
input();
solve();
}
}