[BOJ_2224] 명제증명

설명

---

 

플로이드 와셜 활용한 알고리즘이며 구현 부분이 상당히 귀찮은 문제입니다. char -> int 형으로 관리하고 이를  대소문자마다 다시 int 위치에 위치 시켜야 하므로 이런 부분이 구현 문제처럼 느껴지는 부분입니다. 사실 나머지 주요 로직은 플로이드 와셜을 이용해서 이미 갔던 위치를 다시 거쳐서 가면서 중간 위치에서 갈 수 있는 곳은 연결되었다는 로직으로 하면 됩니다.

코드

---

package shortest_path;

import java.util.*;
import java.io.*;

public class BOJ_2224 {
    private static char itoa(int idx) {
        if (idx<26) return (char)('A'+idx);
        return (char)('a'+(idx-26));
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int map[][] = new int[52][52];

        // 입력 받기
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" => ");
            char from = input[0].charAt(0);
            char to = input[1].charAt(0);

            // 대문자는 0-25, 소문자는 26-51로 매핑
            int fromIndex = Character.isUpperCase(from) ? from - 'A' : from - 'a' + 26;
            int toIndex = Character.isUpperCase(to) ? to - 'A' : to - 'a' + 26;
            map[fromIndex][toIndex] = 1;
        }
        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 || map[i][j] == 1) continue;
                    if(map[i][k] == 1 && map[k][j] == 1)
                        map[i][j] = 1;
                }
            }
        }
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 52; i++) {
            for (int j = 0; j < 52; j++) {
                if (i == j || map[i][j] != 1) continue;
                cnt++;
                sb.append(itoa(i) + " => " + itoa(j) + '\n');
            }
        }
        System.out.println(cnt);
        System.out.println(sb.toString());

    }

}

2224번: 명제 증명