[백준 2458] 키 순서 / 자바 / dfs

#문제         

레벨: G4
알고리즘: dfs 
풀이시간: 
힌트 참조 유무:

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

---

#문제 풀이        

자기가 간접적으로 지목(화살표)을 당해도, 간접적으로 지목(화살표)을해도 그 사람이 나보다 키가 작은지, 큰지 알 수 있다. 그래서 우리는 키 작은 사람을 지목하는 그래프 하나, 키 큰 사람을 지목하는 그래프 하나 두개를 만들어야 한다. 

그 두 개의 그래프를 따로 따로 dfs하여 자기가 알 수 있는 학생의 수를 알아낸다.

 

 

---

#풀이 코드      

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M;
    static List<ArrayList<Integer>> graphBigger, graphSmaller;
    static boolean[] visited;

    public static void main(String[] args) 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());

        graphBigger = new ArrayList<>();
        graphSmaller = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            graphBigger.add(new ArrayList<>());
            graphSmaller.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int smaller = Integer.parseInt(st.nextToken()) - 1;
            int bigger = Integer.parseInt(st.nextToken()) - 1;
            graphBigger.get(smaller).add(bigger);
            graphSmaller.get(bigger).add(smaller);
        }

        int answer = 0;
        for (int i = 0; i < N; i++) {
            visited = new boolean[N];
            int biggerCount = dfs(i, graphBigger) - 1; // 자기 자신 제외

            visited = new boolean[N];
            int smallerCount = dfs(i, graphSmaller) - 1; // 자기 자신 제외

            if (biggerCount + smallerCount == N - 1) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    private static int dfs(int node, List<ArrayList<Integer>> graph) {
        visited[node] = true;
        int count = 1;

        for (int next : graph.get(node)) {
            if (!visited[next]) {
                count += dfs(next, graph);
            }
        }

        return count;
    }
}

 

---

#비슷한 유형      

https://jsw5913.tistory.com/186

[백준 10159] 저울 / 자바 / dfs