[JAVA] 2224 명제 증명 - 트리구조

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

2224번: 명제 증명

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class bj2224 {
    static int N;
    static int MAX_SIZE = 58;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int [][] arr = new int[MAX_SIZE][MAX_SIZE];
        int cnt=0;
        for (int i = 0; i < N; i++) {
            String str = br.readLine(); //한 줄씩 읽고 캐릭터 받아옴
            char first = str.charAt(0);
            char second = str.charAt(str.length()-1);
 
            if(first == second) continue; //문자로 받아온 애들을 숫자로 바꿔서 arr배열에 넣어줌.
            int from = first - 'A';
            int to = second - 'A';
 
            if(arr[from][to] != 1){
                arr[from][to] = 1;
                cnt+=1;
            }
        }
 
        for(int k=0;k<MAX_SIZE;k++){
            for(int i=0;i<MAX_SIZE;i++){
                for(int j=0;j<MAX_SIZE;j++){
                    if(i!=j && arr[i][j] == 0 && arr[i][k] ==1 && arr[k][j] ==1){
                        arr[i][j] =1;
                        cnt+=1;
                    }
                }
            }
        }
        System.out.println(cnt);
        for(int i=0;i<MAX_SIZE;i++){
            for(int j=0;j<MAX_SIZE;j++){
                if(arr[i][j] != 0){
                    System.out.println((char)(i+'A') + " => " + (char)(j+'A'));
                }
            }
        }
    }
}
 

문제를 이해해보자.

여러 가지 명제를 종합하여 삼단 논법을 출력하는 것이 목표이다.

* 이 때, 전건과 후건이 같은 경우( p => p)는 출력하지 않는 것을 주의!

 

--------[시도했으나 잘 안된 것1]---------

명제는 [Alphabet] => [Alphabet]의 형태로 주어지는데, 두 알파벳 사이의 => 앞 뒤에는 공백이 한 칸씩 있다.

처음에는 1. 공백, =, >를 구분자로 하여 StringTokenizer를 이용해 문자열을 구분하는 방법을 사용했으나

StringTokenizer의 사용이 미숙하여 ㅠ_ㅠ 자꾸 안되는것이다... 그래서 생각해보니

문자열의 맨 앞부분과 맨 끝부분이 알파벳이므로, 한 줄씩 읽고 [0]번 째 index와 [length-1]번 째 index를 받아왔다.

----------------------------------------

 

또한 문자로 받아온 애들을 'A'를 빼줘서 int형태로 변경해주었다. 

 

--------[시도했으나 잘 안된 것2]---------

이 때 알파벳의 대문자, 소문자의 총 개수가 각각 26개씩 52개이므로 MAX_SIZE 52인 배열을 생성해

대문자일 경우 0-25, 소문자일 경우 26-51의 index에 치환해주려고 했으나..............

피곤했는지 머리가 잘 돌아가지 않아 OutofRange오류에 허덕이다가 그냥 58칸으로 만들어 주었다.

(대문자와 소문자의 아스키코드 사이에 6개의 문자가 더 있음)

메모리의 낭비는 개발자의 적이지만 어쩔 수 없다.

----------------------------------------

 

연결되었다는 의미로 arr[from][to]의 값을 1로 바꿔주었다.

MaxSize만큼 for문을 돌려야 한다.

먼저, i==j인 경우는 전건과 후건이 같은 경우이므로 항상 참인 명제, 따라서 값을 변경해주지 않아도 된다.

또한 해당 명제는 이미 1인 경우 확인 할 필요가 없으므로 이 부분도 확인해준다.

그 다음 arr[i][k] ==1, arr[k][j]==1, 즉 삼단 논법이 성립해야 하므로 해당 부분까지 확인이 되었을 시에,

*드디어* arr[i][j] ==1을 확인할 수 있다.

 

값을 1로 변경할 때 마다 총 카운트를 세어 출력해주고, arr를 돌면서 값이 1인 애들을 출력해주면 완성!!