c언어 2224번 명제 증명 (백준)

#include <stdio.h>
#define INF 100000000

int main(void)
{
	int n;
	scanf("%d", &n);
	int d[52][52] = {0}; //최단 연결 배열
	
	for(int i=0; i<52; i++) { //배열 초기화
		for(int j=0; j<52; j++) d[i][j] = INF;
	}
	
	while(n--) { //input
		char a, b;
		scanf(" %c => %c", &a, &b);
		if(a <= 'Z') a-='A'; //A~Z -> 0~25로
		else a = a-'a'+26;
		if(b <= 'Z') b-='A'; //a~z -> 26~52로
		else b = b-'a'+26;
		d[a][b] = 1; //a에서 b로 가는 그래프는 존재한다.
	}
	
	for(int k=0; k<52; k++) //Floyd Warshall
	for(int i=0; i<52; i++)
	for(int j=0; j<52; j++) {
		if(d[i][k]+d[k][j] < d[i][j])
		d[i][j] = d[i][k]+d[k][j];
	}
	
	int cnt = 0; //명제의 개수 세기 (그래프의 개수) (단 자기 자신에 대한 것은 제외한다)
	for(int i=0; i<52; i++) {
		for(int j=0; j<52; j++) {
			if(d[i][j] < INF && i!=j) cnt++;
		}
	} printf("%d\n", cnt);
	
	for(int i=0; i<52; i++) { //존재하는 명제 (연결된 그래프)를 알파벳 순으로 출력
		for(int j=0; j<52; j++) {
			if(d[i][j] < INF && d[i][j]) {
				if(d[i][j] < INF && i!=j) {
					char a=i, b=j;
					if(a < 26) a+= 'A';
					else a+='a'-26;
					if(b < 26) b+= 'A';
					else b+='a'-26;
					printf("%c => %c\n", a, b);
				}
			}
		}
	}
}

풀이 : Floyd Warshall

0) 몇 개의 명제를 입력받는가

1) 최단 거리(?)를 담는 배열을 INF로 초기화

2) 명제를 받음 d[a][b] : a가 참이면 b도 참이다. 단 여기서 알파벳을 숫자로 변환해 준다.

3) Floyd Warshall

4) 간선의 개수를 센다. 단 자기 자신 a=>b (a==b)은 제외한다.

5) 모든 간선(명제)을 a => b의 꼴로 출력한다. 단 자기 자신은 제외한다.

 

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

2224번: 명제 증명