실패를 두려워하지 않고
될 때까지 덤비는 🔥
그런 프로그래머 😎

🔗 Link

문제
풀이

💡 Idea

내 풀이 방식

위상정렬하면서 순위가 확실한 것들의 개수를 찾아야 하나 싶었지만, 그건 어려울 것 같았다. 어느 노드가 순위가 정해진 노드인지 판단할 방법이 안 떠오른다.

그래서 다음으로 떠올린 방법은, 그래프를 순회하며, 그 노드에서 내가 이기는 사람의 수와 내가 지는 사람의 수를 세는 것이다. 즉, 내가 이기는 사람의 수 + 내가 지는 사람의 수 == 전체 사람 수 - 1(나) 라면 내 순위가 고정된다는 것을 이용하는 것이다. 식으로 다시 써보면, win[i] + lose[i] == n-1 그러면 어떻게 그래프를 순회해야 이를 잘 셀 수 있을까?

처음에는 위상정렬을 하며, 그 순서에 따라서 승리한 노드 개수를 계속 물려 받는 방식을 생각해 보았는데, 이는 중복되는 승리 노드를 처리를 못해줄 것 같아서 pass. 결국 내가 다른 선수들이랑의 승패 관계를 아는지 중요해서, 단순히 승리 패배 수가 아니라 누구한테 이겼고 졌는지도 저장해야 해서 set을 사용하기로 결정.

그래서 최종 구현 방향은, indegree와 queue를 사용해서 위상정렬을 하며 내가 누구한테 패배했는지 저장하고, outdegree와 queue를 잉ㅇ해서 내가 누구한테 승리했는지 전부 저장.

그리고 이긴 사람 수 + 진 사람 수 == 전체 사람 수 - 1 인 사람의 수를 세기.

GPT의 조언

GPT한테 피드백 받아보니까, 이것도 좋은데 주어진 조건이 100명 이하기 때문에 n^3인 플로이드와셜로 각 노드가 서로에게 도달할 수 있는지 체크하는 방식이 더 단순하게 구현 가능하다고 함. 확실히 모든 노드(사람)들 간에 연결 여부를 파악해야 하는 거니까, 플로이드와셜이 편할 듯.

🔑 Code

import java.util.*;
class Solution {
    public int solution(int n, int[][] results) {
        int[] indegree = new int[n+1], outdegree = new int[n+1];
        ArrayList<Integer>[] adj = new ArrayList[n+1];
        ArrayList<Integer>[] adj2 = new ArrayList[n+1];
        Set<Integer>[] win = new Set[n+1], lose = new Set[n+1];
        for(int i = 1; i <= n; i++){
            adj[i] = new ArrayList<>();
            adj2[i] = new ArrayList<>();
            win[i] = new HashSet<>();
            lose[i] = new HashSet<>();
        }
        ArrayDeque<Integer> q = new ArrayDeque<>();
        
        
        for(int[] result: results){
            int A = result[0];
            int B = result[1];
            indegree[B]++;
            outdegree[A]++;
            adj[A].add(B);
            adj2[B].add(A);
        }
        
        for(int i = 1; i <= n; i++){
            if(indegree[i] == 0) q.offer(i);
        }
        
        // lose 갱신
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int nxt: adj[cur]){
                lose[nxt].addAll(lose[cur]);
                lose[nxt].add(cur);
                if(--indegree[nxt] == 0) q.offer(nxt);
            }
        }
        
        for(int i = 1; i <= n; i++){
            if(outdegree[i] == 0) q.offer(i);
        }

        // win 갱신
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int nxt: adj2[cur]){
                win[nxt].addAll(win[cur]);
                win[nxt].add(cur);
                if(--outdegree[nxt] == 0) q.offer(nxt);
            }
        }
        
        // 정답 계산
        int answer = 0;
        for(int i = 1; i <= n; i++){
            if(win[i].size() + lose[i].size() == n-1) answer++;
        }
        
        return answer;
    }
}

🗨️ Side Notes

참고