[프로그래머스] 순위

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

이 문제도 BFS(너비 우선 탐색)으로 직관적으로 풀 수 있다.
각 선수가 이긴 사람들 / 진 사람들을 BFS로 카운트해주면 된다.
-> BFS를 해서 내가 이긴 사람들의 수를 win이라하고, 나에게 이긴 사람들의 수를 lose라고 했을 때
두 수의 총 합이 n-1이면 다른 선수들과 승/패 관계가 모두 정해졌다는 뜻인걸 이용하면 된다.

코드

---

1. Python

from collections import defaultdict, deque
def solution(n, results):
    win_graph = defaultdict(list)
    lose_graph = defaultdict(list)
    
    for s, e in results:
        win_graph[s].append(e)
        lose_graph[e].append(s)
        
    def bfs(s, graph):
        visited = [False] * (n+1)
        q = deque([s])
        visited[s] = True
        cnt = 0
        
        while q:
            cur = q.popleft()
            for next in graph[cur]:
                if not visited[next]:
                    visited[next] = True                    
                    q.append(next)
                    cnt += 1
        return cnt
    
    answer = 0
    for i in range(1, n+1):
        win = bfs(i, win_graph)
        lose = bfs(i, lose_graph)
        if win + lose == n - 1:
            answer += 1
    return answer

2. JS

function solution(n, results) {
    const winGraph = Array.from({length: n+1}, () => []);
    const loseGraph = Array.from({length: n+1}, () => []);
    
    for(const [s, e] of results){
        winGraph[s].push(e);
        loseGraph[e].push(s);
    }
    
    const BFS = (s, graph) => {
        const visited = Array(n+1).fill(false);
        visited[s] = true;
        const q = [s];
        let head = 0;
        let cnt = 0;
        
        while(head < q.length){
            const cur = q[head++];
            for(const next of graph[cur]){
                if(!visited[next]){
                    visited[next] = true;
                    q.push(next);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    let answer = 0;
    for(let i = 1 ; i <= n ; i++){
        const win = BFS(i, winGraph);
        const lose = BFS(i, loseGraph);
        if(win + lose === n-1) answer++;
    }
    return answer;
}

결과

---