문제 1613번

풀이 접근

1. 문제를 보고 처음에는 최단경로 관련 문제가 아닌 것으로 생각해 N개의 사건을 1차원 배열의 dp로 접근하려고 했다.
2. 최소, 최단 이런 단어는 없지만, case들을 연결하기에 최단경로 알고리즘을 적용하고자 하였고, k와 s의 수가 다른 문제들에 비해 낮은 편이고 시간제한도 2초로 넉넉하여플로이드 워셜 알고리즘으로 풀었다.
3. 사건의 전후 관계에서 전을 start 후를 end라고 하면, dist[start][end]는 앞에 있는 사건이 먼저 일어났으므로 -1, dist[end][start]는 앞에 있는 사건이 늦게 일어났으므로 +1을 넣어준다.
4. 플로이드 워셜 알고리즘을 실행한다.
5. 결과로는 알 수 없는 내용은 0이 나올 것이고, 알 수 있는 내용은 문제의 조건에 맞게 출력될 것이다.

소스코드

import java.io.*;
import java.util.*;
public class boj1613 {
    static int N, K,S;
    static int[][] dist;
    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());
        dist = new int[N+1][N+1];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            dist[start][end] = -1; dist[end][start] = 1;
        }
        floyd_warshall();
        S = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < S; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            sb.append(dist[start][end] + "\n");
        }
        System.out.println(sb.toString());
    }
    public static void floyd_warshall(){
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <=N; i++) {
                for (int j = 1; j <=N; j++) {
                    if(dist[i][k] ==0){
                        if(dist[i][k] ==1 && dist[k][j] ==1){
                            dist[i][j] = 1;
                        }else if(dist[i][k] == -1 && dist[k][j] ==-1){
                            dist[i][j] =-1;
                        }
                    }
                }
            }
        }
    }
}

문제 핵심

• 최단경로
• 플로이드 워셜