[Python] 프로그래머스 순위 | 플로이드-워셜 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

 

문제 해결 포인트

- 플로이드 워셜 알고리즘으로 해결 가능한 문제

- 정점 i가 1부터 N까지 모든 정점으로 갈 수 있다면 순위를 알 수 있다.

- 초기 인접 행렬은 무한수로 초기화, 연관이 있는 두 정점 results는 1로 초기화한다.

  이는 1번에 걸쳐 a 정점과 b 정점이 관계가 있다는 뜻이다.

- a 정점에서 b 정점으로 바로 가는 방법 (a -> b) 또는 k를 거치는 방법 (a -> k -> b) 중 작은 경우로 업데이트

 

- 정점 i에서 j로 가는 방법( 순위가 i보다 j가 크다 ) 또는 j에서 i로 가는 방법 ( 순위가 i보다 j가 작다)

  하나라도 알고 있다면 둘의 상관관계가 존재한다는 의미

 

- 테스트 케이스에서 graph의 상태를 보면 다음과 같다

여기서 앞서 언급했듯 i에서 j로 가는 방법 또는 j에서 i로 가는 두 방법 어느 것도 연결이 없다면(무한수라면)

두 정점의 관계는 없는 것이고, 해당 i 정점은 순위를 알 수 없다.

 

모든 정점과의 관계가 존재하는 경우는 2와 5 두 가지 경우로, 그림으로 살펴보면 다음과 같다

 

 

 

 

⬇ 플로이드 워셜 관련 작성 글을 참고하세요

2023.05.17 - [🧪Computer Science/알고리즘] - [알고리즘] 최단 경로 알고리즘 | 다익스트라 | 플로이드 워셜

 

작성 코드

INF = int(1e9)
def solution(n, results):
    graph = [[INF]*(n+1) for _ in range(n+1)]  # 인접 행렬
    result = 0

    for a, b in results:  # 직접 연관이 있는 관계 업데이트
        graph[a][b] = 1

    # 플로이드-워셜 알고리즘
    for k in range(1, n+1):
        for a in range(1, n+1):
            for b in range(1, n+1):
                # 행 열이 같다면 0, 다르다면 a -> b 와 a -> k -> b 중 짧은 거리 선택
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) if a != b else 0

    for i in range(1, n+1):
        flag = False  # 정점 i에 대해 i -> j 또는 j -> i로 갈 수 있는 방법이 있는지 판별
        for j in range(1, n+1):
            if i != j and graph[i][j] == INF and graph[j][i] == INF:
                flag = True  # 정점 i로부터 도달 할 수 없는 정점이 하나라도 있으면 순위를 알 수 없음
                break
        if not flag:  # i 정점으로부터 모든 정점으로 도달 할 수 있다면
            result += 1

    return result

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚