[BOJ] 백준 2224 : 명제 증명 (java)

🧪 2224 명제 증명

---

난이도 : 🌟 골드 4
유형 : 플로이드-워셜

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

 

📝 문제

---

수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다. 예를 들어 "P이면 Q일 것이다." 라는 명제는 “P => Q” 라는 기호로 표현된다. 이때의 P를 전건, Q를 후건이라고 한다.

논리학에서 어떤 명제를 증명할 때 가장 널리 쓰이는 방법 중 한 가지가 바로 삼단 논법이다. 만약 두 명제 “P => Q", "Q => R" 가 모두 참이면, 명제 "P => R"이 역시 참이 된다. 이러한 방법을 사용했을 때 명제 ”P => R"이 증명되었다고 한다.

어떤 참인 명제가 주어졌을 때, 이 명제가 참이므로 이 명제 자체도 증명될 수 있다고 할 수 있다. 하지만 “P => P”와 같은 명제는 항상 참이 되는데, 이런 식으로 전건과 후건이 같은 경우는 출력하지 않기로 한다.

N개의 참인 명제들이 주어졌을 때, 증명될 수 있는 명제를 모두 구해내는 프로그램을 작성하시오. 명제를 증명하는 방법은 여러 가지가 있을 수 있지만, 위에서 언급한 방법만을 사용하기로 한다.

 

입력

 

첫째 줄에 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 참인 명제들이 주어진다. 명제는 "P => Q"의 꼴로 주어지는데, “=>”는 앞뒤가 공백으로 구분되어 있다. P나 Q는 명제를 나타내는 문자인데, 알파벳 대소문자 한 글자를 사용한다. 같은 명제가 여러 번 주어질 수도 있다.

 

출력

 

첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으로 정렬한다. 알파벳은 대문자가 소문자에 우선한다. 즉, 정렬했을 때 A, B, …, Z, a, b, …, z 순서로 나와야 한다.

 

🧐 핵심 로직 

---

1) 영문자 대문자와 소문자의 개수 52개와 둘 사이의 공백 6개를 포함한 총 58개의 크기를 갖는 2차원 배열을 만들어준다.

 

2) 이때, 전건과 후건이 같은 경우는 0으로 처리하고 다른 배열은 1e9의 값으로 초기화해준다.

 

3) 입력받은 값에 대해 2차원 배열에 대입해주고 이때, 전건과 후건은 순서가 있기 때문에 단방향으로만 값을 넣어준다.

 

4) 플로이드-워셜 방식을 활용해서 모든 정점쌍간의 최단 경로를 구한 후 그 중 1e9와 0이 아닌 부분만 validRelationships 리스트에 넣어준다.

 

5) 출력 양식에 따라 validRelationships 의 size와 문자열을 출력한다.

 

💻 최종 코드 (340 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    static int x;
    static int[][] relationships;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        x = Integer.parseInt(br.readLine());
        relationships = new int[58][58];
        for (int i = 0; i < 58; i++) {
            for (int j = 0; j < 58; j++) {
                relationships[i][j] = (int) 1e9;

                if (i == j) {
                    relationships[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < x; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " => ");
            int p = convertChar(st.nextToken().charAt(0));
            int q = convertChar(st.nextToken().charAt(0));

            if (p != q) {
                relationships[p][q] = 1;
            }
        }

        for (int k = 0; k < 58; k++) {
            for (int i = 0; i < 58; i++) {
                for (int j = 0; j < 58; j++) {
                    relationships[i][j] = Math.min(relationships[i][j], relationships[i][k] + relationships[k][j]);
                }
            }
        }

        List<String> validRelationships = new ArrayList<>();
        for (int i = 0; i < 58; i++) {
            for (int j = 0; j < 58; j++) {
                if (relationships[i][j] != (int) 1e9 && relationships[i][j] != 0) {
                    char a = (char) (i + 'A');
                    char b = (char) (j + 'A');
                    validRelationships.add(a + " => " + b);
                }
            }
        }

        System.out.println(validRelationships.size());

        for (String relationship : validRelationships) {
            System.out.println(relationship);
        }

        br.close();
    }

    private static int convertChar(char c) {
        if (c >= 'A' && c <= 'Z') {
            return c - 'A';
        } else {
            return c - 'a' + 32;
        }
    }
}