백준 2458번
https://www.acmicpc.net/problem/2458

문제

---

생각하기

---

• DFS, floyd-Warshall 문제이다.

• 비대칭적 관계를 그래프로 표시하기 위해서 2개의 그래프를 사용해야 됨

  • 양방향 그래프가 아님을 알아야함
  • 작은키의 방향으로 진행하는 그래프와 큰 키의 방향으로 진행하는 그래프가 구분되어야 함

동작

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            boolean[] isVisited = new boolean[N + 1];

            // i번 노드를 기준으로 큰 사람이 있는지 찾고, 작은 사람이 있는지 찾는다. 
            // 그렇게 해서 만난 노드가 N개가 되면 자신의 순위를 알 수 있다고 판다
            int count = DFS(i, tallList, isVisited) + DFS(i, shortList, isVisited) - 1;

            if (count == N) ans++; // 모두 방문했으면 순서를 알 수 있다.
        }

i번 노드에서 시작해서 자신보다 키가 큰 사람과 작은 사람이 있는 파악해서 파악된 인원수가 N이면 자신의 순서를 알 수 있는 것.

결과

코드

---

DFS

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static List<List<Integer>> shortList;
    private static List<List<Integer>> tallList;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            boolean[] isVisited = new boolean[N + 1];
            int count = DFS(i, shortList, isVisited) + DFS(i, tallList, isVisited) - 1;
            if (count == N) ans++;
        }


        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static int DFS(int node, List<List<Integer>> list, boolean[] isVisited) {
        int count = 1;
        isVisited[node] = true;

        for (int next : list.get(node)) {
            if (isVisited[next]) continue;
            count += DFS(next, list, isVisited);
        }

        return count;
    } // End of DFS()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            tallList.get(a).add(b);
            shortList.get(b).add(a);
        }

    } // End of input()
} // End of Main class

Floyd

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int INF = Integer.MAX_VALUE;
    private static int N, M;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        floyd();

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            boolean flag = true;
            for (int j = 1; j <= N; j++) {
                if (arr[i][j] == INF && arr[j][i] == INF) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                ans++;
            }
        }

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // 각 정점 k에 대해 모든 정점 쌍 (i, j)의 거리를 검토하고 i에서 k를 거쳐 j로 가는 경로가 기존 i -> j 로 가는 경로보다 짧은지 비교한다.

                    if (arr[i][k] == INF || arr[k][j] == INF) continue;

                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

    } // End of floyd()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

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

    } // End of input()
} // End of Main class