[BOJ] 백준 1613번 : 역사 (JAVA)

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

 

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

 

 

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.

 

이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

 

 

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

 

 

풀이

플로이드 와샬 알고리즘을 활용한 문제였습니다. 문제에서는 모든 사건의 전후 관계를 파악해야하기때문에, 모든 정점에 대하여 모든 정점에 도달할 수 있는지 판단할 수 있어야 합니다.

 

따라서 일부 사건의 전후 관계를 입력받은 배열을 플로이드 와샬 알고리즘을 사용하여 모든 사건의 전후 관계를 알도록 확장시키면 됩니다.

 

그리고 s개의 전후 관계를 물어보는 질문이 입력으로 들어오는데, 우리는 -1, 0, 1 중에 하나를 순차적으로 출력해야 합니다.

 

-1인 경우는 x가 y보다 앞선 경우, 즉 x에서 y로 이동할 수 있다는 의미입니다.

반대로, 1인 경우는 y가 x보다 앞선 경우, 즉 x에서 y로 이동할 수 없으나 y에서 x로 이동할 수 있다는 의미입니다.

 

0은 무엇이 있을까요?

물론, x에서 y로, y에서 x로 둘 다 이동할 수 없는 경우도 있지만, 1 ~ N의 범위를 벗어난 값이 입력으로 들어오는 경우도 있습니다.

 

위에 4가지 케이스를 잘 분류하여 출력하면 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        boolean[][] arr = new boolean[N + 1][N + 1];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
 
            arr[x][y] = true;
        }
        
        // 플로이드 와샬 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][k] && arr[k][j]) {
                        arr[i][j] = true;
                    }
                }
            }
        }
        
        int S = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        while(S-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            if(x < 1 || y < 1 || x > N || y > N) { // 주어진 범위에서 벗어날 경우
                sb.append("0\n");
            }else {
                if(arr[x][y]) { // x에서 y로 갈 수 있다는 뜻은 사건이 먼저 일어났다는 뜻
                    sb.append("-1\n");
                }else {
                    if(arr[y][x]) { // y에서 x로 갈 수 있다는 뜻은 사건이 나중에 일어났다는 뜻
                        sb.append("1\n");
                    }else { // x에서 y, y에서 x로 모두 갈 수 없으면 상관 없는 사건 관계임
                        sb.append("0\n");
                    }
                }
            }
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.