13. 순위 JAVA (프로그래머스)

가. 문제파악

 1. 유형 : 그래프

    -   접근을 어떻게 해야할지 감이 잘안왔던 문제, 단순배열의 경우로만 하려다가 그래프로 풀이했다.

 

나. 코드 

 1. 풀이 : 양방향으로 탐색하자!

    -   순위를 확정 지을 수 있는 것은 결국 자신 이외에 사람들과 승패가 갈려야한다.

    -   a-b 에서 b가 승자고 b-c에서 c가 승자면 a-c 에서 승자는 a가 된다.

    -   모든 선수들을 연결하여 그래프 탐색을 하면 위의 경우를 파악할 수 있다.

import java.util.LinkedList;
import java.util.List;

public class Solution {


    public int solution(int n, int[][] results) {
        int answer = 0;
        order = new LinkedList[n];
        reverse = new LinkedList[n];

        for(int i = 0; i < order.length; i++) {
            order[i] = new LinkedList<>();
            reverse[i] = new LinkedList<>();
        }
        for(int i = 0; i < results.length ; i++) {
            int win = results[i][0]-1;
            int lose = results[i][1]-1;
            order[lose].add(win);
            reverse[win].add(lose);
        }

        for(int i = 0; i < n; i++) {
            int sum = 0;
            count = 0;
            visited = new boolean[n];
            explore(i, order);
            sum = count;
            count = 0;
            visited = new boolean[n];
            explore(i, reverse);
            sum+=count;

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

        }
        return answer;
    }
    boolean[] visited;
    List<Integer>[] order;
    List<Integer>[] reverse;
    int count;

    private void explore(int v,List<Integer>[] graph) {

        visited[v] = true;
        for(int adj : graph[v]){
            if(!visited[adj]){
                count++;
                explore(adj,graph);
            }
        }
    }

}

 

 2. 풀이 : 플루이드 와샬

    -   이 풀이가 대부분이라서 요것도 한번 해보았다. 

    -   이알고리즘은 O(N^3) 이므로 범위에 따라 조심히 사용해야 한다.

public class Solution {

     public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] map = new int[n][n];

        for(int i = 0; i < results.length; i++) {
            int win = results[i][0]-1;
            int lose = results[i][1]-1;
            map[win][lose] = 1;
            map[lose][win] = -1;
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n ; i++) {
                for(int j = 0; j < n; j++) {
                    if(i == j || map[i][j]!=0) continue;
                    if(map[i][k] == map[k][j]){
                        map[i][j] = map[i][k];
                    }
                }
            }
        }

        loop : for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
               if(map[i][j] == 0 && i!=j ) continue loop;
            }
            answer++;
        }
        return answer;
    }


}