[Level 3] 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

어떻게 순위를 매길 수 있을까??

 

높이를 구하고

높이 같은 거 있으면 탈락

자기 높이 -1인데 갈 수없다면 탈락

실패

순위에는 관심이 없다

부모 노드들의 개수 + 자식 노드들의 개수 = n-1 이면 순위 특정 가능하다

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;

        int[][] graph = new int[n][n];

        for (int i = 0; i < results.length; i++) {
            graph[results[i][0] - 1][results[i][1] - 1] = 1;
            graph[results[i][1] - 1][results[i][0] - 1] = -1;
        }

        /////////////////////////////////////////////////////////////

        boolean[] visited;

        for (int i = 0; i < n; i++) {
            visited = new boolean[n];

            dfs_child(graph, i, visited);
            dfs_parent(graph, i, visited);

            int count = 0;
            for (int j = 0; j < n; j++)
                if (visited[j]) count++;

            if (count == n - 1)
                answer++;

        }

        return answer;
    }

    public void dfs_child(int[][] graph, int index, boolean[] visited) {

        for (int i = 0; i < graph.length; i++) {
            if (graph[index][i] == 1  && !visited[i]) {
                visited[i] = true;
                dfs_child(graph, i, visited);
            }
        }

    }

    public void dfs_parent(int[][] graph, int index, boolean[] visited) {
        for (int i = 0; i < graph.length; i++) {
            if (graph[index][i] == -1 && !visited[i]) {
                visited[i] = true;
                dfs_parent(graph, i, visited);
            }

        }
    }

}