🔍 문제

📌 입력

📌 출력

💻 제출

🤔 문제 풀이 까지의 생각

일단 정점과 연결선을 통해서 푸는 그래프 문제들은 다양한 풀이방법이 많다.
그중 최단 거리와 같은 키워드가 존재 하는 경우는 bfs, 다익스트라, 플로이드 등등 을 첫번째로 생각한다.

이번 문제는 최단거리 문제가 아니기에 제외 했으며 N의 수가 굉장히 낮아 플로이드 적용이 가능하지 않나..? 라고 생각을 했다.
(floyd warshall은 3중 for문이 필요하기 때문에 시간 복잡도 효율이 매우 안좋다.)

플로이드 문제를 풀때는 항상 연결선 간의 비용이 주어지지만 이번문제의 경우에는 주어지지 않았다.

로직을 돌릴때 확장 할 비용을 연결선 간의 거리 계산이 아니라 양방향 추가 개수 즉 cnt를 저장하기 위한 목적으로 사용한다면 어떨까 하는 생각이 들었다.

예제 데이터를 적용한 정점과 연결선의 관계는 위 이미지와 같을 것 이다.

양방향 연결을 통해서 접근이 가능 한 경우 cnt가 1이 되도록 설정 해주었다.
(s,e 연결이 되도록 예제가 주어졌다면 반대 방향인 e,s의 cnt를 1 추가)

floyd를 통해서 확장을 해준다면 정점 부터 정점 까지 이동하기 위한 모든 양방향 cnt 개수가 정리 될 것 이다.

📝 코드

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    static int N, M,Q;
    static final int INF = 987654321;
    static int[][] distance;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        N = Integer.parseInt(st.nextToken()); //건물 수
        M = Integer.parseInt(st.nextToken()); //관계 선

        distance = new int[N+1][N+1];

        for (int i=1; i<=N; i++){
            for (int j=1; j<=N; j++){
                if (i != j){
                    distance[i][j] = INF;
                }
            }
        }

        for (int i=0; i<M; i++){
            StringTokenizer stD = new StringTokenizer(br.readLine()," ");

            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());
            int rotate = Integer.parseInt(stD.nextToken());


            if (distance[s][e] > 1){
                distance[s][e] = 0;
            }

            distance[e][s] = (rotate == 0) ? 1 : 0;
        }

        floyd();

        Q = Integer.parseInt(br.readLine());

        for (int i=0; i<Q; i++){
            StringTokenizer stD = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());

            bw.write(distance[s][e] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }



    static void floyd(){
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {

                    if (distance[i][j] > distance[i][k] + distance[k][j]){
                        distance[i][j] = distance[i][k] + distance[k][j];
                    }
                }
            }
        }
    }
}