[프로그래머스 level3 순위] 플로이드 워셜 알고리즘 활용하기!

해결해야하는 문제는 다음과 같았다.

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

코딩테스트 연습 - 순위

 

 

 

문제를 읽고 우선 graph를 만들어서 이긴 경우, 진 경우, 비어 있는 경우를 구분하고자 하였다.

따라서 graph에 node1이 node2를 이기면 graph[node1][node2] = 1이 되도록 하였고, 이에 따라 node2가 node1에게 지게 되므로 graph[node2][node1]=2로 하였다.

즉 이기면 1을 저장, 지면 2를 저장하도록 하였다.

 

 

그 다음 플로이드 워셜 알고리즘을 사용하여 채울 수 있는 그래프를 채우고자 하였다. 이를 떠올리게 된 배경은 다음과 같다.

i가 k를 이긴 경우 i>k라고 표기를 하겠다.

 

i > k 이고 k>j인 경우 I>j 일 것이다.

--> graph[i][k] == 1 and graph[k][j]==1 

i< k이고 k<j인 경우 i<j 일 것이다.

--> graph[i][k]==2 and graph[j][k]==1 

그리고 i와 j는 다른 경우에만 1또는 2로 채우므로 마지막에 i!=j라는 조건을 추가해주었다.

 

이러한 방식으로 graph에 채울 수 있는 부분을 채운다.

 

그리고 graph가 완성되었을 때 0번째 열과 자기자신 열을 제외하고 0이 아니라면 순위를 매길 수 있는 경우이기 때문에, 이러한 경우 answer +=1 을 해주었다.

 

이러한 생각으로 작성한 풀이는 다음과 같다.

def solution(n, results):
    answer = 0
    graph = [[0] * (n+1) for _ in range(n+1)]
    
    for winner,loser in results :
        # 이기면 1, 지면 2
        graph[winner][loser] = 1
        graph[loser][winner] = 2
   

    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]==1 and graph[k][j]==1 and i!=j:
                    graph[i][j]=1
                    graph[j][i]=2
                
                elif graph[i][k]==2 and graph[j][k]==1 and i!=j:
                    graph[j][i]=1
                    graph[i][j]=2
                
    for i in range(1,n+1):
        if graph[i].count(0)==2:
            answer += 1
    
    return answer

 

그래프에 있어서 빈 공간을 채울 때 플로이드 워셜을 떠올리면 효율적으로 풀 수 있다는 것에 대해서 다시 한 번 생각해볼 수 있는 계기가 되었다.