c언어 15723번 n단 논법 (백준)

#include <stdio.h>

int main(void) {
	int n, m;
	scanf("%d", &n);
	int d[26][26] = {};
	for(int i = 0; i<26; i++) d[i][i] = 1; //자기자신은 True 

	while(n--) {
		char a, b;
		scanf(" %c is %c", &a, &b);
		a-='a';
		b-='a';
		d[a][b] = 1;
	}
	
	//floyd warshall
	for(int k = 0; k<26; k++) {
		for(int i = 0; i<26; i++) {
			for(int j = 0; j<26; j++) {
				if(d[i][k] == 1 && d[k][j] == 1) d[i][j] = 1;
			}
		}
	}
	
	scanf("%d", &m);
	while(m--) {
		char a, b;
		scanf(" %c is %c", &a, &b);
		a-='a';
		b-='a';
		if(d[a][b]) printf("T\n");
		else printf("F\n");
	} 
}

 

 

풀이 : floyd warshall O(n^3)

0. 그래프는 단방향이다.

1. 문자들을 입력을 받고 -'a'을 하여 0~25까지의 숫자로 변환한다.

2. d[26][26]을 0으로 초기화한 뒤, 입력받은 것들을 1(true)로 바꾼다.

3. 자기자신은 ex) a is a 1을 대입해 준다

4. floyd warshall을 돌린다.

5. m번 동안 입력받은 명제의 d[][] 값이 1이면 T, 아니면 F을 출력한다.