순위

문제

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

코드

import java.util.*;

class Solution {

    int bfs(ArrayList<Integer> g[], int s_idx){
        Queue<Integer> q = new LinkedList<>();
        boolean visit[] = new boolean[g.length];
        int count = 0;
        q.add(s_idx);
        visit[s_idx] = true;
        while(!q.isEmpty()){
            count++;
            int cur_idx = q.poll();
            for(int next_idx : g[cur_idx]){
                if(visit[next_idx] == false){
                    q.add(next_idx);
                    visit[next_idx] = true;
                }
            }
        }
        return count;
    }

    public int solution(int n, int[][] results) {
        int answer = 0;
        int win[] = new int[n+1];
        int lose[] = new int[n+1];
        ArrayList<Integer> win_g[] = new ArrayList[n+1];
        ArrayList<Integer> lose_g[] = new ArrayList[n+1];

        for(int i=1; i<=n; i++){
            win_g[i] = new ArrayList<>();
            lose_g[i] = new ArrayList<>();
        }
        for(int[] result : results){
            win_g[result[0]].add(result[1]);
            lose_g[result[1]].add(result[0]);
        }


        for(int i=1; i<=n; i++){
            int count = 0;
            int count2 = 0;
            count += bfs(win_g, i);
            count2 += bfs(lose_g, i);
            if((count+count2) == n+1)
                answer++;
        }

        return answer;
    }
}

피드백

• 아, 위상정렬 (topology sort, 멋있다.) 인줄 알았는데 절대 아니었다.
  • 현재 큐의 사이즈 만큼 위상정렬해서 만약에 현재 큐에 노드가 하나만 있으면 얘는 순위가 정해진 아이다. 라고 생각을 했지만
  • 응 아니었다. 그냥 문제의 예제가 반례이다.
• 결론은 O(N^3)의 완전 탐색을 풀 수 있었다.
  • 이기는 그래프, 지는 그래프를 따로 만들어서 각각 탐방할 수 있는 노드를 세서 자신을 포함하면 N+1 만큼 나오면 순위가 정해진 아이다.