1613번 문제

문제

풀이

모든 사건 쌍 간의 관계를 알아야 하므로 플로이드-워셜 알고리즘을 사용한다.
사실 이 문제는 이전에 풀었던 저울문제 랑 매우 유사해서 빠르게 풀어낼 수 있었다.

어떤 사건 a, b, c가 있고, 이 중 둘 간의 관계만 알려져 있다고 가정해보자. 예를 들어, a>b라는 비교 결과만 알고 있다.
여기서 b와 c의 비교 결과(R)가 하나 더 주어지면 a와 c의 관계를 알아낼 수 있다.

위 내용을 잘 생각해보면, 반드시 b>c가 되어야 함을 알 수 있다. b<c이라면 'a>b, c>b' 이므로 a와 c중 무엇이 더 큰지를 알아낼 수 없다.

따라서 [a,b] 를 방문할 때, a와 b의 관계가 [b,c]에서 b,c의 관계와 동일하다면, [a,c]의 관계를 정립할 수 있다.
(즉, [a,b]에서 a>b임을 확인, [b,c]에서 b>c임을 확인하면 a>c임을 알아낼 수 있음)

코드

package shortestpath;

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

public class Boj1613_역사 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken()); // 사건의 개수
        int k = Integer.parseInt(st.nextToken()); // 알고 있는 사건의 전후 관계 개수
        int[][] matrix = new int[n+1][n+1];
        for(int i=0; i<k; i++) {
            st = new StringTokenizer(br.readLine());
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());
            matrix[before][after] = -1;
            matrix[after][before] = 1;
        }

        for(int m=1; m<=n; m++) {
            for(int i=1; i<=n; i++) {
                if(matrix[i][m]==0) continue; // 알 수 없는 관계
                for(int j=1; j<=n; j++) {
                    if(matrix[m][j]==0) continue; // 알 수 없는 관계
                    if(matrix[i][m]*matrix[m][j] == 1) { // 부호가 같으면
                        matrix[i][j] = matrix[m][j];
                    }
                }
            }
        }

        int s = Integer.parseInt(br.readLine()); // 알고자 하는 사건 관계 수
        for(int i=0; i<s; i++) {
            st = new StringTokenizer(br.readLine());
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());
            sb.append(matrix[before][after]).append("\n");
        }

        System.out.println(sb);
    }
}

• int[][] matrix에 각 사건의 전후 관계를 저장한다.
  - matrix[i][j]가 -1이라면 i가 j보다 선행, +1이라면 j가 i보다 선행, 0이라면 알 수 없음을 의미한다.
• 모든 쌍을 탐색해가며 추가적으로 알 수 있는 사건 관계를 저장한다.