[6월 2주차] 1문제 풀이

[그래프] 순위 (Lv.3)

걸린 시간

1시간 초과

접근 방식

results의 승패 하나하나를 순서대로 승자가 parent, 패자가 child로 가는 방식으로 풀어보려고 했으나, 서로 다른 연결점을 가질 때 순위 비교를 하거나 1→2와 1→3이 나왔는데 2→3이 나왔다면 3 입장에서는 parent가 1과 2인데 이 둘의 크기를 어떻게 확인해야할까? 와 같은 의문점이 많이 남았다.

만약 1 / 6, (4 / 3) / 2 / 5 에서 [4, 6]이 추가된다면?

1 / 4 / (6, 3) / 2 / 5 이지만 1과 6에도 연결고리가 있는데 이건 어떻게 없애야할까?

이런 의문점에 갇혀 여러가지 방법을 생각해보았지만 논리적으로 깔끔해질 수가 없었다.

결국 1시간 내에 해결방법을 찾지 못하고 해설을 찾아보았다.

삼단 논법하면 떠오르는 플루이드 워셜 알고리즘을 사용하는 것이었다.

정답 코드

def solution(n, results):
    answer = 0
    check = [[0] * n for _ in range(n)]

    for win, lose in results:
        check[win - 1][lose - 1] = 1

    for k in range(n): # 거치는 점
        for i in range(n): 
            for j in range(n):
                if i == j or j == k or i == k:
                    continue
                if check[i][k] == 1 and check[k][j] == 1:
                    check[i][j] = 1

    for i in range(n):
        count = 0
        for j in range(n):
            if check[i][j] == 1 or check[j][i] == 1:
                count += 1
        if count == n - 1:
            answer += 1

    return answer

배운점

플루이드 워셜 알고리즘은 이럴 때 사용한다.

• 모든 지점 간 최단 거리 계산: 단 한 번의 출발점이 아니라, 네트워크에 있는 모든 노드 사이의 최단 경로를 전부 알아야 할 때 씁니다.
• 음수 가중치 허용: 간선의 비용이 음수일 때도 사용할 수 있습니다. (단, 음수 사이클이 없어야 합니다.)
• 노드 개수가 적을 때: 다이나믹 프로그래밍을 기반으로 하며, 시간 복잡도는 O(N³)입니다. 노드 개수가 500개 이하 정도로 적을 때 효율적으로 동작합니다.

이 문제는 노드(사람)이 100 이하라서 사용 가능한 알고리즘이었다.

그렇다해도 최단 거리같은 문제는 아니었어서 떠올리기는 어려웠을 것 같다.

이 문제에 이 알고리즘으로 문제가 대체 왜 해결되는지 이해하는데에 1~2시간을 투자한 것 같았다….