[프로그래머스lv.3] 순위

 

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

풀이

 

그래프를 그려본다.

 

그래프를 그려보고 경로가 다른 노드들과 모두 이어져 있는 노드를 찾는다. 

 

 4는 모든 녀석과 이어져 있다. 1은 3을 모르고 2는 6을 모르고 3은 1을 모르고 5는 3을 모르고 6은 2를 모른다.

여기서 4라는 모든 경로와 이어진 노드를 어떻게 찾을 수 있을까?

 

플로이드 와샬을 활용하면 된다.

플로이드 와샬은 모든 노드의 최단거리를 찾아준다.

그 점을 이용해서 노드가 이어져 있는지를 확인한다. 최단거리가 존재하지 않다면 경로가 없다는 것이다.

 

백준의 [2458번]키순서와 문제가 같다.

시간복잡도

 

플로이드 와샬의 시간복잡도와 같다. for문 3개를 중첩해서 사용하기에 O(n^3)이다.

 

 

코드

def solution(n, results):
    INF = 9873654321
    mat = [[0 if i==j else INF for i in range(n+1)] for j in range(n+1)]



    for result in results:
        a,b = result
        mat[a][b] = 1

    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if i==j:
                    mat[i][j] = 0
                else:
                    mat[i][j] = min(mat[i][j],mat[i][k] + mat[k][j])
    
    for i in mat:
        print(i)
    print()

    connect=[1]*(n+1)
    connect[0] = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if mat[i][j] == INF and mat[j][i] == INF:
                connect[i] = 0
                connect[j] = 0
    
    return sum(connect)