[코딩테스트] 백준 - n단 논법

n단 논법 15723번 [16일차]

시간제한	메모리 제한
2초	128MB

문제

모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.

지무근은 중앙대 컴퓨터공학부 학생이다.

그러므로 지무근은 미인이다.

위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, n개의 전제가 있을 때 m개의 결론을 도출할 수 있을 것이다. 이때의 n과 m은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자.

 

입력

첫째 줄에 정수 n(2 ≤ n ≤ 26)이 주어진다.

둘째 줄부터 n개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만 모든 전제는 “모든 a는 b이다”라는 의미이다. 하지만 “모든 b는 a이다”의 의미는 될 수 없다. 또한 a는 b이면서 c일 수 없으나, a와 b가 동시에 c일 수는 있다.

n + 2번째 줄에 정수 m(1 ≤ m ≤ 10)이 주어진다. 그 다음 m개의 줄에 걸쳐 각 줄에 하나의 결론이 전제와 같은 형식으로 주어진다.

 

출력

m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.

 

나의코드

package day16;

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

// n단 논법 - 15723번
public class Solution2 {

    static Map<String, String> map;

    public static void main(String[] args) throws IOException {
        // 입력
        // 첫번째줄 n개의 전재
        // a -> b -> c -> d
        // HashMap을 이용해 정보들 저장
        // 기준 알파벳 , 연결된 알파벳

        // 기능
        // 큐를 이용 bsf
        // 단방향 표
        // 기준 알파벳 , n단 논법에 적용될 알파벳들 저장


        // 출력
        // m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력
        //참일 경우 T, 거짓일 경우 F

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        map = new HashMap<>();

        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" is ");
            String start = line[0];
            String end = line[1];

            // 입력받은 값들 hashmap에 넣기
            map.put(start, end);
        }

        StringBuilder sb = new StringBuilder();

        //출력
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String[] line = br.readLine().split(" is ");
            String start = line[0];
            String end = line[1];

            // 출력
            if (bfs(start, end)) { // 조건이 맞을 경우
                sb.append("T").append("\n");
            } else {
                sb.append("F").append("\n");
            }
        }

        System.out.println(sb);

    }

    static boolean bfs(String start, String end) {
        Queue<String> queue = new LinkedList<>();
        Set<String> arr = new HashSet<>();
        queue.offer(start);
        arr.add(start);


        while (!queue.isEmpty()) {
            String now = queue.poll();
            if (now.equals(end)) {
                return true;
            }

            if (map.containsKey(now)) {
                String next = map.get(now);
                if (!arr.contains(next)) {
                    queue.offer(next);
                    arr.add(next);
                }
            }
        }
        return false;
    }
}