백준 2224 - 명제 증명

문제

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

리뷰

플로이드-워셜로 풀이할 수 있는 간단한 문제였다.

우선 주어진 영어 대소문자 입력값을 인덱스로 표현하기 위해 플로이드 워셜에
사용되는 map을 52 x 52의 크기로 선언하고, 0~25까지의 인덱스로 대문자를
26~51까지의 인덱스로 소문자를 표현하였다. 대문자의 경우 문자 입력에서 A를
뺴주면 바로 인덱스 값이 나오고 소문자의 경우는 a를 빼준다음 26을 더해주면
된다.

명제는 방향 그래프에서의 간선으로 표현할 수 있고, 문자를 인덱스로 매핑해주는
convert 로직을 활용하여 map[i][j]의 값을 갱신한 뒤 플로이드-워셜 로직을
실행하면 명제 성립이 되는 경우(정점간 이동이 가능한 경우) map[i][j]의 값이
Integer.MAX_VALUE가 아니게 된다.

최종적으로, 이중 for 문을 돌며 정점간 경로가 존재하는 경우만 map에서
출력해주면 성립하는 모든 명제를 구할 수 있다.

로직의 시간복잡도는 플로이드-워셜의 $O(52^3)$으로 수렴하므로 $N=10000$인
최악의 경우에도 무난히 제한 조건 2초를 통과할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    /**
     * 알파벳 총 개수 52개(대소문자)
     * 인덱스:
     * - 대문자 0~25
     * - 소문자 26~51
     */
    static final int SIZE = 52; 
    static int[][] map = new int[SIZE][SIZE];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < map.length; i++)
            for (int j = 0; j < map.length; j++) {
                if (i == j) continue;

                map[i][j] = MAX_VALUE;
            }

        int N = parseInt(br.readLine());
        StringTokenizer st;
        char c1, c2;
        int i, j;

        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            c1 = st.nextToken().charAt(0);
            st.nextToken();
            c2 = st.nextToken().charAt(0);

            i = convert(c1);
            j = convert(c2);
            map[i][j] = 1;
        }

        floyd();

        List<String> ans = new ArrayList<>();
        StringBuilder sb;
        for (i = 0; i < map.length; i++)
            for (j = 0; j < map.length; j++) {
                if (i == j) continue;

                if (map[i][j] == MAX_VALUE)
                    continue;

                sb = new StringBuilder();
                c1 = (char) (i < 26 ? i + 'A' : i - 26 + 'a');
                c2 = (char) (j < 26 ? j + 'A' : j - 26 + 'a');
                sb.append(c1).append(" => ").append(c2);
                ans.add(sb.toString());
            }
        System.out.println(ans.size());
        for (String str : ans) {
            System.out.println(str);
        }
        br.close();
    }

    static int convert(char c) {
        if (Character.isUpperCase(c))
            return c - 'A';

        return c - 'a' + 26;
    }

    static void floyd() {
        for (int k = 0; k < map.length; k++)
            for (int i = 0; i < map.length; i++)
                for (int j = 0; j < map.length; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE)
                        continue;

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
    }
}

결과