(Week8)[플로드이드-워셜] 공항

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 30분 

1. 문제 설명

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

프로그래머스

선수들의 경기 결과를 통해서 명확한 순위를 알 수 있도록 구하는 문제이다. 만약 세 명의 선수가 있을 때, A 선수가 B선수에게 이겼고 B선수가 C선수에게 이겼다고 가정하자. 그러면 A 선수가 1등, B선수가 2등, C선수가 3등이다. A선수의 경우 C 선수와 싸우지 않고도 경기 결과를 알 수 있다. 

2. 접근 방식

https://summa-cum-laude.tistory.com/16 글 참고

• 해당 문제의 핵심적인 이론은 다른 선수들의 결과를 종합해서 또 다른 선수의 결과를 알 수 있다는 것이 쟁점이다. 
• 플로이드 워셜 알고리즘 이용
• 중간 매개변수가 되는 것을 가장 처음 for문으로 만든다. 
• 선수 a가 c를 이기고, c가 b를 이기면 선수 a는 b를 이김
• 선수 a가 c에게 지고, c가 b에게 지면 선수 a는 b에게 짐

3. 코드

from collections import Counter
def solution(n, results):
    score = [[0]*(n+1) for _ in range(n+1)]
    for p1, p2 in results:
        score[p1][p2] = 1
        score[p2][p1] = -1
    for pk in range(1, n+1):     # 기준 선수k 선택
        for pa in range(1, n+1): # 점수판 순회 시작
            for pb in range(1, n+1): # 만약 선수a가 선수k를 이기고, 
                                      # 선수k가 선수 b를 이기면, a가 b를 이긴게 됨
                if score[pa][pk] == 1 and score[pk][pb] ==1:
                    score[pa][pb] = 1
                elif score[pa][pk] == -1 and score[pk][pb] ==-1:
                    score[pa][pb] = -1
    ans = 0
    for i in range(1, n+1):
        if Counter(score[i])[0] == 2:
            ans += 1
    print(score)
    return ans

4. 코멘트

• 해당 문제의 경우 이해와 구현은 비교적 쉬웠으나, 해결을 위한 알고리즘을 생각하기까지가 조금 어려웠다. 
• 결국 a와 c가 싸운 결과를 확인하기 위해, a와 b의 결과 b와 c의 결과로 b를 중간 매개변수로 활용한다는 점에서 플로이드-워셜로 푼다는 게 꽤 센세이션했다.
• 알고리즘 문제 만드는 사람들 진짜 똑똑이들...