[프로그래머스] LEVEL3 순위

문제

문제 링크

문제 해결 접근

[1] 문제 출제 포인트

• 그래프 알고리즘 카테고리에 있는데, 해당 방법으로 풀 방법이 전혀 생각나지 않아서 검색했다.
• 결론은, 플로이드-워셜 알고리즘으로 접근하는 것이 포인트였다.
• a가 k를 이겼다면 k는 항상 a보다는 아래 순위이고, k가 c를 이겼다면 c도 항상 k보다 아래 순위이다.
• 이렇게 두 가지 관계가 이어질 수 있다면 (a-> k, k-> b는 결국 a -> k -> b라고 할 수 있다.), 우리는 여기서 6가지의 관계를 알 수 있다.

• 이 문제에서의 포인트는 "a와 b는 관련이 없어보이지만, k 가 중간에 끼게 되면 관련성을 업데이트할 수 있다!" 라는 점에서 플로이드-워셜을 떠올리는 것이다.

[2] 문제 해결 포인트

• 위에서 설명한 개념을 적용하여 플로이드-워셜로 모델링을 한다면,
  1) a -> k -> b 의 관계를 발견하면 (1번, 2번의 관계)
  2) 나머지 4개의 관계에 대하여 2차원 배열에 저장해준다. (3~6번의 관계)
• 마지막에 2차원 리스트를 모두 확인하면서, 자기 자신을 빼고 모든 결과를 알고 있다면, 확실하게 순위를 알 수 있는 것으로 생각하고 결과를 출력한다.

정답 코드

def solution(n, results):
    answer = 0
    graph = [[0]*(n) for _ in range(n)]
    
    for a,b in results:
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = -1
    
    for k in range(n):
        for a in range(n):
            for b in range(n):
                
                if a == b or graph[a][b] in [1,-1]: ## 자기 자신이거나, 이미 둘의 승패를 알고 있다면 넘어가기 
                    continue
                
                if graph[a][k] == graph[k][b] == 1: ## a가 k를 이기고, k가 b를 이긴 것이 있으면
                    graph[a][b] = 1 ## a가 b를 이긴 것
                    graph[b][a] = -1 ## b가 a에게 진 것 
                    graph[k][a] = -1 ## k는 a에게 진 것 
                    graph[b][k] = -1 ## b는 k에게 진 것 
    
    for line in graph:
        if line.count(0) == 1: ## 자기 자신 빼고 모든 결과를 알고 있으면 순위를 알 수 있음 
            answer += 1
    
    return answer

느낀 점

• 사실 처음에는 문제를 보고 아예 그래프로 접근할 생각조차를 못했다. a,k,b의 삼중 관계를 하나로 묶어낼 수 있는 문제가 있다면, 플로이드-워셜을 생각해보는 것도 필요할 것 같다.
• 해당 문제는 노드가 100, 엣지가 4500개 정도인데도 삼중for문을 사용할 수 있었다!
• 접근 방식 자체를 새롭게 배운 것 같아서 흥미로웠다.