[백준/JAVA] 15723번: n단 논법

📖 문제

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

 

 

 

💡  풀이 방식

• 플로이드-워셜

 

i는 k고, k는 j면, i는 j다.

 

- N개의 전제를 입력받으며 a는 b라고 처리한다. → connected[a][b] = true

- 플로이드-워셜로 i는 k고, k는 j면, i는 j 가 되도록 처리한다.

- M개의 결론이 맞는지 확인하며 a는 b라면(= connected[a][b] == true) T를, 아니라면 F를 출력한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        boolean[][] connected = new boolean[26][26];
        
        while(N --> 0) {
            String[] str = br.readLine().split(" is ");
            char a = str[0].charAt(0);
            char b = str[1].charAt(0);
            
            connected[a - 'a'][b - 'a'] = true;
        }
        
        // 플로이드-워셜
        for(int k = 0 ; k < 26 ; k++) {
            for(int i = 0 ; i < 26 ; i++) {
                for(int j = 0 ; j < 26 ; j++) {
                    if(i == j || j == k || k == i)  continue;
                    
                    // i → k고, k → j면, i → j다.
                    if(connected[i][k] && connected[k][j]) {
                        connected[i][j] = true;
                    }
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int M = Integer.parseInt(br.readLine());
        while(M --> 0) {
            String[] str = br.readLine().split(" is ");
            char a = str[0].charAt(0);
            char b = str[1].charAt(0);
            
            sb.append(connected[a - 'a'][b - 'a'] ? "T" : "F");
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
}
 

 

 

➕ 다른 풀이 방식

BFS로도 풀 수 있다.

백준 15723번 n단 논법 (JAVA)

---

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---