[자바] 백준 2224 - 명제 증명 (java)

 문제 : boj2224

---

 

필요 알고리즘 개념

• 플로이드 와샬 (Floyd Warshall)
  • O(N^3)이라 자주 못쓰지만, 쓸 수만 있으면 모든 정점에서 모든 정점으로의 최단경로 파악 혹은 길이 존재하는지 파악이 한방에 가능한 가장 강력한 탐색 알고리즘(대신 느림ㅋ) 플로이드 와샬을 쓸 수 있는 문제이다!! 구현도 엄청 간단하므로 플로이드 와샬을 써보자.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  a => b 형태일 경우, a에서 b로 가는 간선을 연결하는 것으로 생각해보자. 그리고 a~z, A~Z를 모두 숫자로 변경하자. 이 때 변경방식은 A~Z를 0~25, a~z를 26~51로 하면 된다. 그래야 출력 시 순서대로 출력해주기가 편하다. 변경 방식은 코드의 atoi, itoa를 참고하자.

 

  간선은 인접행렬로 표현할꺼다. boolean[][] arr에 대해, arr[a][b]가 true일 경우 a에서 b로 가는게 가능함을 나타낸다. 그럼 이제 로직은 다음과 같다.

 

1. 입력을 받으면서 a => b 형태일 경우 arr[a][b] = true로 한다.

2. 플루이드 와샬 알고리즘을 적용한다.

3. arr을 순회하면서 arr[a][b]가 true라면 출력해준다.

 

플로이드 와샬만 안다면 매우 간단한 로직임을 알 수 있다. 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    private int atoi(char c) {
        if (c>='a') return c-'a'+26;
        return c-'A';
    }
    private char itoa(int idx) {
        if (idx<26) return (char)('A'+idx);
        return (char)('a'+(idx-26));
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        boolean[][] arr = new boolean[52][52];
        while (n-->0) {
            String cur = br.readLine();
            arr[atoi(cur.charAt(0))][atoi(cur.charAt(5))] = true;
        }
        for (int k = 0; k < 52; k++) {
            for (int i = 0; i < 52; i++) {
                for (int j = 0; j < 52; j++) {
                    if (i==j || i==k || k==j || arr[i][j]) continue;
                    if (arr[i][k] && arr[k][j]) arr[i][j] = true;
                }
            }
        }
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 52; i++) {
            for (int j = 0; j < 52; j++) {
                if (i == j || !arr[i][j]) continue;
                cnt++;
                sb.append(itoa(i)).append(' ').append('=').append('>').append(' ').append(itoa(j)).append('\n');
            }
        }
        bw.write(String.valueOf(cnt));
        bw.newLine();
        bw.write(sb.toString());
        bw.flush();
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}