[프로그래머스] 순위

문제 설명

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

문제 풀이

• DFS를 이용하여 풀이하였다.
• 문제의 가장 큰 인사이트는 선수 간의 관계를 단방향 그래프로 나태냈을때, 그래프에서 특정 선수와 다른 모든 선수가 도달이 가능하면 해당 선수는 순위를 나타낼 수 있다는 점이다.
• DFS를 이용하여 모든 선수 간의 도달 가능 여부를 인접행렬로 만들어 주었다.
• 이후 해당 인접행렬을 이용하여 다른 모든 선수와 도달 가능한지 확인하여 카운트했다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N;
    public boolean[][] reachable;
    public List<List<Integer>> map = new ArrayList<>();

    //방문 했던 노드면 : before와 현재 노드 이후 노드 모두 연결
    //처음 방문 : 현재 노드 before에 추가하고 dfs 진행
    public void dfs(int cur, List<Integer> before) {
        //방문 했던 노드
        if (reachable[cur][cur]) {
            for (int i = 1; i <= N; i++) {
                if (reachable[cur][i]) {
                    for (int j = 0; j < before.size(); j++) {
                        int num = before.get(j);
                        reachable[num][i] = true;
                    }
                }
            }
            return;
        }

        List<Integer> nextBefore = new ArrayList<>(before);
        nextBefore.add(cur);
        //처음 방문 하는 노드
        for (int i = 0; i < before.size(); i++)
            reachable[before.get(i)][cur] = true;
        for (int i = 0; i < map.get(cur).size(); i++) {
            int next = map.get(cur).get(i);
            dfs(next, nextBefore);
        }
        reachable[cur][cur] = true;
    }

    public int solution(int n, int[][] results) {
        //초기화
        N = n;
        reachable = new boolean[N+1][N+1];
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());
        for (int[] result : results) {
            int from = result[1];
            int to = result[0];
            map.get(from).add(to);
        }

        //모든 노드 도달 가능 여부 계산
        for (int i = 1; i <= N; i++)
            dfs(i, new ArrayList<>());

        //다른 모든 노드와 도달 가능한지 확인
        int result = 0;
        for (int i = 1; i <= N; i++) {
            boolean flag = true;
            for (int j = 1; j <= N; j++) {
                if (i == j) continue;
                if (!reachable[i][j] && !reachable[j][i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) result++;
        }
        return result;
    }
}