백준 10159 (저울) - java

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

10159번: 저울

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

public class Main {
    static int n = 0;
    static int m = 0;

    static boolean[][] big = new boolean[101][101]; // k번째 보다 작은수에 대해 search
    static boolean[][] small = new boolean[101][101]; //k번째 보다 큰 수에 대해 search

    static boolean[] visit =new boolean[101]; // 방문 배열

    static int result = 0;
    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());
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());

        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            big[x][y] = true; // x는 y보다 크다
            small[y][x] = true; // y는 x보다 작다
        }

        visit[1] = true;
        for(int i=1;i<=n;i++) {
            search(i); // i보다 작은 수 찾기
            search2(i); // i보다 큰 수 찾기
            System.out.println(n -1 -result);
            visit = new boolean[101]; // 방문 배열 초기화
            result = 0; // 개수 초기화
        }
    }
    
    static void search(int k)
    {
        for(int i=1;i<=n;i++)
        {
            if(k==i)
                continue;

            if(!visit[i])
            {
                if(big[k][i]) // 해당 수 보다 작은 수를 찾은 경우
                {
                    visit[i] = true; // 방문 처리
                    result++;
                    search(i); // dfs
                }
            }
        }
    }

    static void search2(int k)
    {
        for(int i=1;i<=n;i++)
        {
            if(k==i)
                continue;

            if(!visit[i])
            {
                if(small[k][i]) // 해당 수보다 큰 수를 찾은 경우
                {
                    visit[i] = true;
                    result++;
                    search2(i); // dfs
                }
            }
        }
    }
}

플로이드-워셜 알고리즘으로 푼 경우도 있다 . 하지만 문제를 봤을 때 직관적으로 푼 풀이를 올렸다.