[Baekjoon] 1613. 역사(Gold 3)[Java]

1613번: 역사

 

문제

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해보자.

 

풀이

사건의 전후 관계를 알고 싶은 사건의 쌍을 (s,e)라 할 때, s가 먼저 일어났으면 -1 / e가 먼저 일어났으면 1 / 모르겠으면 0 을 출력해야 합니다.

이는 특정 지점 s에서 e로 갈 수 있으면 -1

e에서 s로 갈 수 있으면 1

갈 수 없으면 0

을 출력해야 하는 문제와 동일하게 생각할 수 있습니다.😊

 

시간 복잡도의 주체가 되는 입력 값 n이 최대 400으로 크기 않으니, 플로이드 와샬 알고리즘을 이용해 풀 수 있을거 같습니다.

플로이드 와샬을 이용해 s에서 e로 가는 경로가 있다면 True 값을, 없다면 False로 나타내도록 하겠습니다.

🌹 이번 문제는 오랜만에 Java로 풀어보았습니다. 파이썬으로는 계속 시간초과가 되어서...😭

정말 오랜만이라서, Java 기본 코드 적는거부터가 일이네요.ㅠㅠ

입력과 출력 기능만 하는 백준 Java의 기본 코드부터 작성해보겠습니다.

import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
    	// 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.close();
    }
}

이제 입력 값을 바탕으로 플로이드 와샬을 사용해, 경로 유무를 확인해보겠습니다.😆

 

코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]); // 사건의 개수
        int m = Integer.parseInt(str[1]); // 사건 연관관계 개수

        // s사건 이후에 e 사건이 발생한 것을 알 때 True, 아니면 False
        boolean[][] history = new boolean[n][n];
        for (int i = 0 ; i < m ; i++) {
	        str = br.readLine().split(" ");
            int s = Integer.parseInt(str[0]);
            int e = Integer.parseInt(str[1]);
    
            history[s-1][e-1] = true;
        }

        // 사건 연관관계를 직접 알지 못해도, 다른 연관관계를 통해 알 수 있는
        // 사건들은 다시 true로 처리
        for (int k = 0 ; k < n ; k++) {
	        for (int i = 0 ; i < n ; i++) {
    	        for (int j = 0 ; j < n ; j++) {
        	        if (history[i][k] && history[k][j]) {
                    	history[i][j] = true;
                    }        
                }
            }
        }
        
        int q = Integer.parseInt(br.readLine());
        for (int i = 0; i < q; i++) {
            str = br.readLine().split(" ");
            int s = Integer.parseInt(str[0]);
            int e = Integer.parseInt(str[1]);
            
            if (history[s-1][e-1]) {
                bw.write(Integer.toString(-1));
                bw.newLine();
            } else if(history[e-1][s-1]) {
                bw.write(Integer.toString(1));
                bw.newLine();
            } else {
                bw.write(Integer.toString(0));
                bw.newLine();
            }
        }
        bw.close();
    }
}