Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 순위

[순위]

접근 과정

접근 1. 트리에서 unique한 depth를 가진 노드의 수가 아닐까?

→ 당장 예시만 봐도 아니다(…)

접근 2. indegree + outdegree가 $n-1$인 노드에 대해, 진출하는 간선을 타고 더 이상 그 합이 $n-1$인 노드가 나타나지 않을 때까지 indegree를 재귀적으로 갱신

• 왜 $n-1$?
  

보조정리 1.
승패관계를 각각 $out$, $in$이라 하자. 어떤 선수 $i$의 승패관계의 합 $out[i]+in[i]$가 $n-1$이라면 그 선수의 순위를 정확히 매길 수 있다.

증명.
선수 $i$의 승패관계의 합이 $n-1$임에도 불구하고, 선수 $i$의 순위를 정확히 매길 수 없다고 가정하자. 이 가정이 참이라면, $i$가 정확히 어떤 위치에 있을지 알 수 없는 상황이 발생해야 하지만, $out[i]$에 속하는 선수들은 항상 $i$보다 낮은 순위에 위치하고, $in[i]$에 속하는 선수들은 항상 $i$보다 높은 순위에 위치한다. (모든 경기 결과에는 모순이 없으므로, 승패관계의 합이 $n-1$이라는 것은 자기 자신을 제외한 모든 선수와의 승패관계가 명확하다.) 이는 가정에 모순이다.

→ 그러나 이 접근은 시작할 때부터 $in[i]+out[i]$가 $n-1$이 아닌 경우 순위를 매길 수 있음에도 순위를 매길 수 없다고 여겨질 수 있고, 시작할 땐 존재하더라도 재귀적으로 갱신하는 과정에서 일부 노드에 대해서만 갱신이 이루어지기 때문에 순위를 매길 수 있음에도 순위를 매길 수 없다고 여겨질 수 있는 경우가 있다.

접근 3. (풀이)

접근 2를 고민하다 생각한 방법이다. BFS/DFS로 모든 노드 $i$에 대해 $out[i]$, $in[i]$를 갱신한 다음, $out[i]+in[i]$가 $n-1$인 $i$의 개수를 세어준다.

다음 보조정리를 이용한다.

보조정리 2.
$p$선수가 $q$선수를 이기고, $q$선수가 $r$선수를 이긴다면 항상 $p$선수는 $r$선수를 이긴다. (Directed Acyclic Graph)

증명.
$p$선수가 $r$선수에게 진다고 가정하자. $p$선수가 $q$선수를 이긴 경기 결과가 있다면 $p$선수는 $q$선수를 항상 이긴다. (∵ 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이기므로)
같은 논리로, $q$선수가 $r$선수를 이긴 경기 결과가 있다면 $q$선수는 $r$선수를 항상 이긴다.
삼단논법을 적용하면, $p\rightarrow q$이고 $q\rightarrow r$이면 $p \rightarrow r$인데, 이는 가정에 모순이다.

이는 선수간의 승패관계는 순환하지 않음(사이클이 존재하지 않음)과 동치이다. (모든 경기에는 모순이 존재하지 않는다는 말이 이 말이다.) 따라서 BFS/DFS를 이용하여 여러 단계에 걸친 승패관계를 모든 노드에 대해 갱신하면서, 승패관계의 합이 $n-1$인 $i$의 개수를 세어주면 된다.

Solution 1. BFS $O(2V(V+E))$

from collections import defaultdict, deque

def bfs(adj, v):
    visited = set()
    queue = deque([v])
    while queue:
        for nxt in adj[queue.popleft()]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)
    return len(visited)

def solution(n, results):
    adj_win, adj_lose = defaultdict(set), defaultdict(set)
    
    for w, l in results:
        adj_win[w].add(l)
        adj_lose[l].add(w)
    
    return sum(1 for v in range(1, n+1) if bfs(adj_win, v) + bfs(adj_lose, v) == n-1)

• visited의 역할은, BFS 과정에서 얻는 방문한 노드를 삽입함으로써 방문 처리의 역할을 겸하고, 방문한 노드의 개수를 $O(1)$에 반환할 수 있게 해 준다.
  • 리스트를 이용하여 방문처리를 하는 방식이었다면, True의 개수를 세는 식으로 $O(V)$가 걸리는 것에 비해 빠르다.
  • 위의 보조정리를 통해 순환하지 않는 그래프임을 알 수 있으므로 시작 노드를 visited에 삽입하지 않고 BFS를 시작해도 문제가 없으며, 시작 노드를 visited에 삽입한다는 것은 자기 자신에 대해 이긴다는 것을 의미하게 되므로 그래서도 안 된다(?).

Solution 2. Set $O(2V^2)$

from collections import defaultdict

def solution(n, results):
    adj_win, adj_lose = defaultdict(set), defaultdict(set)

    for w, l in results:
        adj_win[w].add(l)
        adj_lose[l].add(w)

    for i in range(1, n+1):
        for w in adj_lose[i]: adj_win[w].update(adj_win[i])
        for l in adj_win[i]: adj_lose[l].update(adj_lose[i])

    return sum(1 for i in range(1, n+1) if len(adj_win[i]) + len(adj_lose[i]) == n-1)

• 다른 사람의 풀이를 보다가 발견했다. 나와 아이디어는 비슷한데, 굳이 BFS를 할 게 아니라 단순히 집합을 합치면(확장하면) 코드도 간결해지고, 훨씬 빨라진다.
• $adj_{lose}[i]$에는 $i$ 선수를 이긴 선수들 $w$가 집합에 담겨 있는데, 이를 $w$가 이긴 선수들인 $adj_{win}[w]$에 $adj_{win}[i]$를 update()해줌으로써 승패관계를 갱신해 나간다. 이는 그 반대의 경우에 대해서도 마찬가지이다.

---

Memo

• 정해는 Floyd-Warshall인 것 같다. 아직 몰라서,,, 일단 공부하던 거 마저 하고 해야겠다!