[프로그래머스]순위

이것 참 뭔가 노드의 관계가 주어진 것 같다.

이는 Directed Graph로 풀 수 있을 것 같다

• 풀이법 생각

  • "정확하게 순위를 매길 수 있는 " 선수의 수..

  • 정확하게 순위를 매길 수 있다는 것은. 모든 노드들과의 확실한 관계가 있는 것을 의미하는가?????

    • MATRIX가 채워져 있는 경우를 의미한다. 무슨말이냐면 그림과 같이 matrix를 채운다.
    • r→ v , 즉 r이 v를 이기는 경우 O를 치고, 이 경우, matrix[v][r]은 x를 친다.
    • 이 관계가 주어지지 않은 곳은 비어있게 된다
    • 즉, 어떤 row에 빈 칸이 없으면, 순위가 확정되었음을 의미한다.

  • 일단 효율성을 생각하지 않겠다.

    

    - 주어진 results를 이용해서 그래프를 생성한다. ( Adjacent list로 만든다)
    - adjacent matrix를 생성한다 : -1로 초기화
        - v1 —> v2 까지 경로가 있는 경우 : v1이 v2에게 이기는 것 —> 1을 저장
            - v2 —> v1은 지는 것이기 때문에 0을 저장한다.
        - 모든 경우를 완료 한 후, matrix[v1] row에 대해 -1 이 하나도 존재하지 않는 경우 —> 순위가 확정된 것 을 의미한다.
    - 이 graph를 이용하여 adjacent matrix 정보를 채워나간다.
        - 각 노드에 대해 완전탐색 한다.
        - BFS를 통하여, v1 —> v2 까지의 경로가 있는지 하나하나 탐색한다.
    - 완전탐색 을 완료 한 후, 초기값이 남아있지 않는 선수의 수를 카운트한다.

    import java.util.*;
    
    class Solution {
        public int solution(int n, int[][] results) {
            int answer = 0;
            int[][] matrix = new int[n][n];
            for(int i=0;i<matrix.length;i++){
                Arrays.fill(matrix[i],-1);
            }
    
            ArrayList<LinkedList<Integer>> graph = new ArrayList<>(n);
            // results 를 이용하여 graph 를 생성한다.
            for(int i=0;i<n;i++)
                graph.add(new LinkedList<>());
            // results의 row별로 값을 얻어온다.
            for(int r=0;r<results.length;r++){
                int win = results[r][0]-1;
                int lo = results[r][1]-1;
                graph.get(win).add(lo);
            }
            // 완전 탐색. 각 노드에 대해
            for(int v=0;v<n;v++){
                bfs(v,graph,matrix);
            }
            for(int v=0;v<n;v++){
                boolean fill =true;
                for(int col=0;col<n;col++){
                    if(matrix[v][col]<0) {
                        fill = false;
                        break;
                    }
                }
                if(fill) answer++;
            }
    
            return answer;
        }
        //
        public void bfs(int start,ArrayList<LinkedList<Integer>> graph,int[][] matrix){
            int[] visit = new int[graph.size()];
            Queue<Integer> q = new LinkedList<>();
            visit[start]=1;
            q.add(start);
            matrix[start][start] = 0;
            while(q.isEmpty()==false){
                int cur = q.poll();
                Iterator<Integer> it = graph.get(cur).iterator();
                while(it.hasNext()){
                    int next = it.next();
                    if(visit[next]==1)continue;
                    //System.out.println(start+1+"--> "+(next+1));
                    visit[next]=1;
                    matrix[start][next]=1;
                    matrix[next][start]=0;
                    q.add(next);
                }
            }
    
        }
    }

ver02

• 처음부터 matrix로만 풀 수 있는가?
• 내가 인접리스트를 따로 만든 이유 : matrix는 bfs를 할 때, 인접한 노드를 탐색하기 위해 , 무조건 매번 O(n)의 탐색을 해야하기 때문이었는데. 이렇게 해도 되긴하다

import java.util.*;
class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] matrix = new int[n][n];
        for(int i=0;i<matrix.length;i++){
            Arrays.fill(matrix[i],-1);
        }
        for(int r=0;r<results.length;r++){
            int win = results[r][0]-1;
            int lo = results[r][1]-1;
            matrix[win][lo] =1;
        }
        for(int start=0;start<n;start++)
            bfs(start,matrix);
        for(int r=0;r<n;r++){
            boolean flag = true;
            for(int col=0;col<n;col++){
                if(matrix[r][col]<0){
                    flag = false;
                    break;
                }
            }
            if(flag) answer++;
        }
        return answer;
    }
    //
    public void bfs(int start,int[][] graph){
        int[] visit = new int[graph.length];
        Queue<Integer> q = new LinkedList<>();
        visit[start]=1;
        q.add(start);
        graph[start][start] = 0;
        while(q.isEmpty()==false){
            int cur = q.poll();
            for(int col=0;col<graph.length;col++){
                if(visit[col]>0) continue;
                if(graph[cur][col]<=0) continue;
                //System.out.println(start+1+"--> "+(col+1));
                visit[col]=1;
                graph[start][col]=1;
                graph[col][start]=0;
                q.add(col);
            }
        }

    }
}