[프로그래머스] 순위/Python - Lv.3

❓문제

프로그래머스

 

📌유형

그래프, Floyd-Warshall

✍🏻풀이

1) 그래프 자료구조 사용
- 이긴 그래프와 진 그래프를 인접 리스트 형태로 만듦.
- 1은 2번을 이김. 1번의 이긴 그래프에 2번에게 진 5번 노드를 업데이트.
- 1은 누구에게도 지지 않음.
- 2번은 5번을 이기고, 1, 3, 4번에게 짐. 1, 3, 4번 이긴 그래프에 5번을 업데이트.
  5번 진 그래프에는 1, 3, 4번을 업데이트.
- 각 노드의 이긴 그래프와 진 그래프의 길이의 합이 n - 1과 같다면 answer를 1 증가.

2) Floyd-Warshall
- 1번이 2번을 이김. graph[2][1]을 1로 초기화. 이와 같이 진 부분은 1로 초기화.
- 그래프를 따라 DP를 활용하여 최소 경로 계산.
- INF가 아닌 경우, 즉 순위를 정할 수 있다면 count를 1 증가.
- count가 n-1과 같다면 answer을 1 증가.

💻코드

# 그래프 자료구조 사용
from collections import defaultdict

def solution(n, results):
    answer = 0
    win, lose = defaultdict(set), defaultdict(set)

    for i, j in results:
        win[i].add(j)
        lose[j].add(i)

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

    for i in range(1, n + 1):
        if len(win[i]) + len(lose[i]) == n - 1:
            answer += 1

    return answer

# Floyd-Warshall

def solution(n, results):
    answer = 0
    INF = 1e9
    
    graph = [[INF] * (n + 1) for _ in range(n + 1)]
    
    for i, j in results:
        graph[j][i] = 1 
    
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                graph[i][j] = 0
                
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
                
    for i in range(1, n + 1):
        count = 0
        for j in range(1, n + 1):
            if graph[i][j] != INF or graph[j][i] != INF:
                count += 1 
        if count == n:
            answer += 1
    
    return answer

💡새로 배운 내용

Floyd-Warshall
- 가중치 그래프에서 모든 노드의 가장 짧은 경로를 찾음.
- 양•음수 가중치 그래프에서 모두 사용 가능.
- 방향, 무방향 가중치 그래프에서 사용 가능.
- 모든 노드 사이의 가장 짧은 경로를 구하기 위해서는 가능한 모든 노드에 대하여 DP로 가능한 경로를 확인.
- 네트워크 및 연결 문제를 해결하는 데 용이.

Pseudo-Code
------------------------------------------------------------------------------------------------
For i = 0 to n – 1
For j = 0 to n – 1
Distance[i, j] = min(Distance[i, j], Distance[i, k] + Distance[k, j])

where i = source Node, j = Destination Node, k = Intermediate Node