백준 1613. 역사 :: 돼지개발자

출처 : https://www.acmicpc.net/problem/1613

"플로이드와샬!"

사건의 전후 관계에 대해 묻고 있다. 플로이드와샬은 음수 가중치를 계산할 수 있다는 점이 다익스트라와 다르다. 문제에서 친절히 -1,0,1 과 같이 힌트를 주었다. 주어지는 사건 x,y 에 대해 1 과 -1 을 부여한다. x y 순으로 주어진다면 아래와 같다.

map[x][y] = 1 ;

map[y][x] = -1;

그렇 다면 x y 두 사건의 관계를 x < y 라고 하자. 이렇게 되면 이제 우리가 찾아야 할 것은 x < (...) < y 의 관계를 만족하는 다른 사건들과의 관계 이다.

이를 아래와 같이 계산한다. 가장 바깥쪽 for문이 우리가 찾을 (...) 에 해당한다. 

for (int a = 1; a <= n; a++) {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if(map[i][a] == 0 || map[i][a] != map[a][j])

continue;

map[i][j] = map[i][a];

}

}

}

위에 소스는 다음과 같은 의미이다. 

i < a 이고 i < a && a < j 라면, 당연히 i < j 가 성립한다.

i > a 이고 i > a && a > j 라면, 당연히 i > j 가 성립한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
    
    static int n,k,s;
    static int[][] map;
    static int[] p;
    static StringBuffer sb = new StringBuffer();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n  =Integer.parseInt(st.nextToken());
        k  =Integer.parseInt(st.nextToken());
        
        map = new int[n+1][n+1];
        
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            map[a][b] = -1;
            map[b][a] = 1;
        }
        
        for (int a = 1; a <= n; a++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if(map[i][a] == 0 || map[i][a] != map[a][j])
                        continue;
                    map[i][j] = map[i][a];
                }
            }
        }
        
        s = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < s; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(map[a][b]+"\n");
        }
        System.out.println(sb);
    }
}