[백준] 2617번 : 구슬 찾기

2617번: 구슬 찾기

---

[DFS]

입력 N은 홀수로만 주어지기 때문에 중간을 (n + 1) / 2로 표현한듯 하다.

 

int[100][2] 배열을 준비하여 int[i][0]에는 i 구슬보다 가벼운 구슬, int[i][1]에는 i 구슬보다 무거운 구슬의 개수를 저장하도록 한다.

 

n회 반복문을 돌며 현재 구슬의 무거운 구슬의 개수 또는 가벼운 구슬의 개수가 (n + 1) / 2개 이상일 때 그 구슬은 가운데의 구슬에 들어갈 수 없다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visit;
    static int[][] dp = new int[100][2];
    static List<Integer>[] list = new ArrayList[100];

    static void DFS(int current, int start){

        visit[current] = true;

        for(int next : list[current])
            if(!visit[next]) {
                dp[start][0]++; //0 : 나보다 가벼운거
                dp[next][1]++; // 1 : 나보다 무거운거
                DFS(next, start);
            }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int half = (n + 1) / 2;
        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }

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

            int heavy = Integer.parseInt(st.nextToken());
            int light = Integer.parseInt(st.nextToken());

            list[heavy].add(light);
        }

        for(int i=1; i<=n; i++) {
            visit = new boolean[100];
            DFS(i, i);
        }

        int result = 0;
        for(int i=1; i<=n; i++)
            if(dp[i][0] >= half || dp[i][1] >= half)
                result++;

        System.out.println(result);
    }
}