[BOJ2617] 구슬 찾기 (플로이드 워셜, 최단 경로)

---

문제 링크 

https://www.acmicpc.net/problem/2617

2617번: 구슬 찾기

 

문제 풀이 

문제 지문에 " 무게가 중간이 절대로 될 수 없는 구슬의 수 " 키워드 였다.

풀어서 적어보자면 자기보다 크거나 작은 구슬의 개수가 중간 개수가 넘어가면 절대 중간이 될 수 없는 구슬이다.

 

- 플로이드 워셜 풀이 

- 시간 복잡도 : O(N^3) + O(N^2)   // 플로이드 워셜 알고리즘 + 각 구슬별로 크거나 작은 구슬 카운팅

- 구슬 절반 개수 : ( N + 1 ) / 2

 

입력 초기화시 i 가 j 보다 큰 경우 floyd[j][i] = 1 로 초기화 하였다. 아래는 플로이드 워셜 결과이다.

각 구슬마다 본인 보다 큰 구슬은 0이상의 값을 가짐 (INF는 비교 불가 뜻함)

0	1	INF	2	1
INF	0	INF	1	INF
INF	INF	0	1	INF
INF	INF	INF	0	INF
INF	INF	INF	INF	0

 

그리고 

1) floyd[i][j] > 0 이면 나보다 큰 구슬의 개수를 하나 증가 시킨다

2) floyd[j][i] > 0 이면 나보다 작은 구슬의 개수를 하나 증가 시킨다

3) 구슬의 개수 절반 이상으로 큰 구슬이 많거나, 작은 구슬이 많은 경우 중간 구슬이 될 수 없으므로 결과값 카운트를 증가 시킨다

4) 결과값 출력

 

제출 코드

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

public class Main {
    
    static int N, M;
    static int[][] floyd;

    static int INF = 100;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        floyd = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++) {
            Arrays.fill(floyd[i], INF);
            floyd[i][i] = 0;
        }

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            floyd[to][from] = 1;

        }
    }

    static void pro() {
        for(int k = 1; k <= N; k++) {
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= N; j++) {
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }

        int ans = 0;
        int limit = (N + 1) / 2; // 구슬 개수의 반 
        for(int i = 1; i <= N; i++) {
            int high = 0;
            int low = 0;
            for(int j = 1; j <= N; j++) {
                if(floyd[i][j] != INF && floyd[i][j] > 0) high += 1;
                else if(floyd[j][i] != INF && floyd[j][i] > 0) low += 1;
            }

            if(high >= limit || low >= limit) ans += 1;
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}