[DFS] 5643. 키 순서 (Java)

[SWEA] 5643. 키 순서

📌 풀이 과정

DFS 탐색을 통해 간접적인 비교까지 확인할 수 있다.
즉, A < B이고, B < C라면, A < C라는 간접 관계도 탐색을 통해 확인 가능하다.

1. graph[from][to] = 1 인접 행렬을 설정한다.
   from 학생이 to 학생보다 키가 작음을 의미한다.

2. 자신보다 키가 큰 학생을 찾는 탐색
   taller(i, visited)는 학생 i보다 키가 큰 학생을 찾는다.
   DFS로 현재 학생에서 출발하여 모든 키가 더 큰 학생들을 재귀적으로 탐색한다.

3. 자신보다 키가 작은 학생을 찾는 탐색
   shorter(i, visited)는 학생 i보다 키가 큰 학생을 찾는다.

4. 자신보다 키가 큰 학생의 수 + 키가 작은 학생의 수 = 전체 학생수 (N-1)
   이 학생의 키 순서는 확실하게 알 수 있는 것이다.

✨ 제출 코드

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

public class Solution {

    static int N, M, ans, tCnt, sCnt;
    static int[][] graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int t = 1; t <= T; t++) {
            N = Integer.parseInt(br.readLine()); // 학생 수
            M = Integer.parseInt(br.readLine()); // 키 비교 횟수
            graph = new int[N+1][N+1];

            StringTokenizer st;
            for(int i = 0; i < M; i++){
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                graph[from][to] = 1; // from < to : 나보다 큰거 저장
            }

            ans = 0;
            for(int i = 1; i <= N; i++){
                tCnt = 0;
                sCnt = 0;
                taller(i, new boolean[N+1]);
                shorter(i, new boolean[N+1]);

                if(tCnt + sCnt == N - 1) ans++;
            }

            System.out.println("#" + t + " " + ans);
        }
    }

    static void taller(int cur, boolean[] visited){
        visited[cur] = true;
        for(int i = 1; i <= N; i++){
            if(!visited[i] && graph[cur][i] == 1){
                tCnt++;
                taller(i, visited);
            }
        }
    }

    static void shorter(int cur, boolean[] visited){
        visited[cur] = true;
        for(int i = 1; i <= N; i++){
            if(!visited[i] && graph[i][cur] == 1){
                sCnt++;
                shorter(i, visited);
            }
        }
    }
}