[Java/플로이드워셜] SWEA. 키 순서

SW Expert Academy

🤔 Intuition

완전 아이디어 싸움인 문제라고 생각한다. 내 풀이는 2초 정도 걸리는 풀이인데, 어떤 사람은 300ms에 풀었더라. 방법이 여러가지일 것 같은데, 나는 거진 완탐 방식으로 푼 셈이다.

 

플로이드 워셜을 이용하여 각 노드 간 연결성을 앞뒤로 체크해줬다. 유향그래프이므로, 내 노드가 모든 노드를 타고 갈 수 있는지를 판별하면 된다. 여기서 포인트는 플로이드 워셜은 아닌데, 그냥 로직 간단하게 구성하려고 플로이드 워셜 썼다.

 

🔎 Algorithm & Complexity

* @algorithm floyd warshall
* @time O(V^3) : 2,075 ms
* @memory O(V^2) : 106,272 kb

👨🏻‍💻 Logic

중요 포인트는 기본 방향으로 인접 노드 정보를 저장해두고, 역방향으로도 저장해둬야 하는 점이다. (자식을 알아야 하니까)

그렇게 플로이드워셜 다 돌리고, 모든 노드에 닿을 수 있는 노드 개수만 세주면 된다. (INF 거리가 남아있는 노드 제외)

// 2,033 ms, 104,412 kb
public class SWEA_키순서 {
    private static int N, M;
    private static int a, b;

    private static int[][] from;
    private static int[][] to;
    public static final int INF = (int) 1e9;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            from = new int[N+1][N+1];
            to = new int[N+1][N+1];

            Arrays.stream(from)
                    .forEach(i -> Arrays.fill(i, INF));
            Arrays.stream(to)
                    .forEach(i -> Arrays.fill(i, INF));

            M = Integer.parseInt(br.readLine());
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                from[a][b] = 1;
                to[b][a] = 1;
            }



            // 연결 구조가 나왔으니, 서로 연결되어 있는지 여부를 체크
            // 플로이드워셜로 풀어서 한 노드라도 거리를 알 수 없는 녀석은 out
            for (int k = 1; k <= N; k++) {
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= N; j++) {
                        from[i][j] = Math.min(from[i][j], from[i][k] + from[k][j]);
                    }
                }
            }

            for (int k = 1; k <= N; k++) {
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= N; j++) {
                        to[i][j] = Math.min(to[i][j], to[i][k] + to[k][j]);
                    }
                }
            }
            int ans = 0;
            top:
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) {
                        continue; // 자기자신은 생략
                    }
                    if (from[i][j] == INF && to[i][j] == INF) { // 양쪽 다 모르면
                        continue top; // next node
                    }
                }
                ans++;
            }
            sb.append(String.format("#%d %d\n", tc, ans));
        }

        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}