[BAEKJOON 백준] 1613 역사

www.acmicpc.net/problem/1613

1613번: 역사

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

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

 

 

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

 

먼저 입력되는 값의 전후 사건이 입력이 된다.

그 입력되는 값을  boolean 배열을 통해서 전 후 사건의 경우 true 로 만들어 준다.

그렇게 만들어진 배열에서 solution 이라는 매서드를 통해서 이어지는 사건들도 true로 만들어 줘야 한다.

 

 

solution을 거치면서 새로운 true가 생기는 것을 알 수 있다.

새롭게 생긴 true는 1,2 와 2,4 가 true이기 때문에 1,4도 true 이라는것을 표시해 준것이다.

이렇게 완성된 배열을 이용해서 먼저 일어난 사건이 true로 되어있고, 먼저 일어난 사건인 경우 -1을 출력하게 된다. 따라서, 1, 5 의 경우 사건이 일어나지 않았기 때문에 0이 되고, 2,4 의 경우 사건이 일어났는데 2가 먼저 일어나서 -1이 출력이 된다.

3,1 의 경우 false이지만, 1,3이 true이기 때문에 뒤에 사건이 먼저 일어난 것을 알 수 있다. 따라서, 1을 출력하게 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
   static int N, K;
   static boolean dist[][];
   public static void main(String[] args) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken());
      dist = 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());
         dist[x][y] = true;
      }
      
      solution();
      StringBuilder sb = new StringBuilder();
      K = Integer.parseInt(br.readLine());
      for(int i=0; i<K; i++) {
         st = new StringTokenizer(br.readLine());
         int x = Integer.parseInt(st.nextToken());
         int y = Integer.parseInt(st.nextToken());
         if(dist[x][y]) sb.append("-1\n");
         else if(dist[y][x]) sb.append("1\n");
         else sb.append("0\n");
      }
      System.out.println(sb.toString());
      
   }
   private static void solution() {
      for(int k=1; k<=N; k++) {
         for(int i=1; i<=N; i++) {
            if(!dist[i][k]) continue;
            for(int j=1; j<=N; j++) {
               if(dist[k][j]) dist[i][j]=true;
            }
         }
      }
   }
}