문제

링크

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았을때, results를 읽고
정확하게 순위를 매길 수 있는 선수의 수를 return 할 것.

※ results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미이다.

---

이전 코드

BFS 알고리즘을 사용한 풀이

from collections import deque

def solution(n, results):
    win_graph = [[] for _ in range(n+1)]
    lose_graph = [[] for _ in range(n+1)]
    
    for a, b in results:
        win_graph[a].append(b)
        lose_graph[b].append(a)
    
    def bfs(start, graph):
        visited = [False] * (n+1)
        queue = deque([start])
        visited[start] = True
        count = 0
        
        while queue:
            cur = queue.popleft()
            
            for next_node in graph[cur]:
                if not visited[next_node]:
                    visited[next_node] = True
                    queue.append(next_node)
                    count += 1
        
        return count
    
    answer = 0
    
    for i in range(1, n+1):
        win_count = bfs(i, win_graph)
        lose_count = bfs(i, lose_graph)
        
        if win_count + lose_count == n - 1:
            answer += 1
    
    return answer

---

new 풀이

플로이드-워셜 알고리즘을 사용한 풀이

※ 플로이드-워셜 : 중간 정점을 하나씩 거쳐 보며, 그래프의 모든 정점 쌍 사이의 관계를 한 번에 구하는 알고리즘

BFS는 한 출발점에서 퍼져 나가는 One-To-All 방식이고, 플로이드-워셜은 모든 쌍을 한 번에 구하는 All-To-All 방식이다.

i가 k를 이기고 k가 j를 이기면, i는 j를 이긴다"는 규칙으로 모든 선수 쌍의 승패 관계를 확인해야 했던 권투 문제에는 플로이드-워셜이 더 적합했다.

BFS로도 모든 쌍을 구할 수 있지만, 선수마다 탐색을 반복해야 해서 비효율적이기 때문이다.

---

---

new 코드

def solution(n, results):
    # 내가 이긴 사람들을 저장하는 그래프
    win_graph = [[False] * (n+1) for _ in range(n+1)]
    # 나를 이긴 사람들을 저장하는 그래프
    lose_graph = [[False] * (n+1) for _ in range(n+1)]
    
    # 승패그래프
    for a, b in results:
        win_graph[a][b] = True   
        lose_graph[b][a] = True  
    
    # 플로이드 워셜 함수로 간접 승패 관계 채우기
    def floyd(graph):
        for k in range(1, n+1):          # 거쳐 가는 노드
            for i in range(1, n+1):      # 출발 노드
                for j in range(1, n+1):  # 도착 노드
                    if graph[i][k] and graph[k][j]:
                        graph[i][j] = True   # 간선
    
    floyd(win_graph)
    floyd(lose_graph)
    
    answer = 0
    
    # 모든 선수에 대해 확인
    for i in range(1, n+1):
        # i가 이긴 사람 수
        win_count = sum(win_graph[i])
        # i가 진 사람 수
        lose_count = sum(lose_graph[i])
        
        # 순위를 매길 수 있는 선수라면 answer에 1추가
        if win_count + lose_count == n - 1:
            answer += 1
    
    return answer`

---

결론

사실 나는 플로이드-워셜을 최단 거리를 구할 때 사용하는 알고리즘으로만 알고 있었다.

그런데 오늘 문제를 풀면서, 거리를 구하지 않고 노드와 노드가 서로 이어져 있는지 확인하는 데에도 플로이드-워셜을 사용할 수 있다는 것을 알게 되었다.

알고리즘을 이름이나 용도만 외울 것이 아니라, 어떤 상황에서 활용할 수 있는지 다양한 사례를 접해봐야겠다는 생각을 했다.