백준 2224 [자바] java 명제 증명

문제 링크: https://www.acmicpc.net/problem/2224

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 순서로 나와야 한다.

▶해설

for(int i=0; i<n; i++){
    String[] split = br.readLine().split(" => ");
    char start = split[0].charAt(0);
    char end = split[1].charAt(0);
    list[start].add(new Node(end));
}

•  다익스트라를 사용하기 위해 list[]배열에 도착점을 넣어줍니다.

for(int i=0; i<'z'+1; i++){
    if(!list[i].isEmpty()){
        bfs(i);
        changeSetToList(i);
        makeResult(sb, i);
        Arrays.fill(visit,false);
    }
}

• list [i]가 비어있지 않다면 명제 관계가 있는 것이므로 bfs(start)를 돌려줍니다.

public static void bfs(int start){
    PriorityQueue<Node> queue = new PriorityQueue<>();
    for(Node node: list[start]){
        queue.add(node);
    }

    while (!queue.isEmpty()){
        Node poll = queue.poll();
        if(!visit[poll.end]){
            temp[start].add(poll.end);
            visit[poll.end]=true;
            for(Node node: list[poll.end]){
                queue.add(node);
            }
        }
    }
}

• temp []는 Set 배열에 도착점을 넣어줍니다. (Set을 사용하면 중복되는 명제를 거를 수 있습니다.)  
• bfs를 돌리며, 도착점을 queue에 넣어 다음 도착점이 존재한다면 계속해서 진행합니다.

private static void changeSetToList(int i) {
    result[i]= new ArrayList<>(temp[i]);
    Collections.sort(result[i]);
}

• Set은 순서가 없으므로 순서대로 출력할 수가 없습니다. 따라서 List로 바꿔줍니다.

private static void makeResult(StringBuilder sb, int i) {
    for(Integer a: result[i]){
        if((char) i ==(char)(int)a){
            continue;
        }
        sb.append((char) i +" => "+(char)(int)a).append("\n");
        count++;
    }
}

• if 문을 통해서 A => A와 같은 자신으로 가는 명제는 걸려주며, 명제 개수를 세는 count를 증가시키며 StringBuilder에 형식에 맞춰 추가합니다.

▶전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


class Node implements Comparable<Node>{
    int end;

    public Node( int end) {
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return this.end-o.end;
    }
}
public class Main {

    static int n;
    static List<Node>[] list;
    static boolean[]visit;
    static Set<Integer>[] temp;
    static List<Integer> []result;
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        list= new ArrayList['z'+1];
        temp = new Set['z'+1];
        visit = new boolean['z'+1];
        result = new ArrayList['z'+1];
        for(int i=0; i<'z'+1; i++){
            list[i]=new ArrayList<>();
            temp[i] = new HashSet<>();
            result[i]=new ArrayList<>();
        }

        for(int i=0; i<n; i++){
            String[] split = br.readLine().split(" => ");
            char start = split[0].charAt(0);
            char end = split[1].charAt(0);
            list[start].add(new Node(end));
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<'z'+1; i++){
            if(!list[i].isEmpty()){
                bfs(i);
                changeSetToList(i);
                makeResult(sb, i);
                Arrays.fill(visit,false);
            }
        }
        System.out.println(count);
        System.out.println(sb.toString());
    }

    public static void bfs(int start){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        for(Node node: list[start]){
            queue.add(node);
        }

        while (!queue.isEmpty()){
            Node poll = queue.poll();
            if(!visit[poll.end]){
                temp[start].add(poll.end);
                visit[poll.end]=true;
                for(Node node: list[poll.end]){
                    queue.add(node);
                }
            }
        }
    }

    private static void changeSetToList(int i) {
        result[i]= new ArrayList<>(temp[i]);
        Collections.sort(result[i]);
    }

    private static void makeResult(StringBuilder sb, int i) {
        for(Integer a: result[i]){
            if((char) i ==(char)(int)a){
                continue;
            }
            sb.append((char) i +" => "+(char)(int)a).append("\n");
            count++;
        }
    }
}