[프로그래머스/Python] 순위 - Level3

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

코딩테스트 연습 - 순위

이 문제는 처음봤을 때 이기고 지는 관계이므로 선후관계가 있다고 생각해서 위상정렬을 사용해서 풀어야겠다고 생각했었다. 위상정렬로 풀려고보니 위상정렬을 사용하기 위한 조건을 만족하지 못했다. 다른 사람의 풀이를 보고 사용한 알고리즘만 확인했다. 플로이드 워셜 알고리즘을 사용하면 풀 수 있었다. 예전에 공부한 것을 바탕으로 문제를 풀었다.

def solution(n, results):
    answer = 0
    graph = [[0] * (n+1) for _ in range(n+1)] # 승패여부를 저장할 그래프
    
    # 이기면 1, 지면 -1로 그래프에 저장
    for win, lose in results:
        graph[win][lose] = 1
        graph[lose][win] = -1
    
    # 플로이드 워셜 수행
    for k in range(1, n+1):
        for a in range(1, n+1):
            for b in range(1, n+1):
                if a != b and graph[a][b] == 0: # 자기 자신이 아니면서 아직 승패여부를 알 수 없는 노드라면
                    if graph[a][k] == 1 and graph[k][b] == 1: # a가 k를 이기고 k가 b를 이기면 a가 b를 이김 
                        graph[a][b] = 1 
                    elif graph[a][k] == -1 and graph[k][b] == -1: # a가 k에게 지고 k가 b에게 지면 a가 b에게 짐 
                        graph[a][b] = -1

    # 순위를 매길 수 있는 선수 세기
    for i in range(1, n+1):
        if graph[i][1:].count(0) == 1:
            answer += 1
                
    return answer

1. 승패 여부를 저장할 그래프를 생성한다. (선수 번호와 인덱스를 맞추기 위해 n+1까지 생성함)

2. results 를 돌면서 이기면 1, 지면 -1 를 그래프(graph)에 저장한다.

3. 플로이드 워셜 알고리즘을 수행한다.

    3-1. 자기 자신이 아니면서 아직 승패 여부를 알 수 없는 노드라면 승패 여부를 따질 수 있는지 확인한다.

    3-2. a가 k를 이기고 k가 b를 이기면 a가 b를 이기므로 graph[a][b] = 1 로 만들어준다.

    3-3. a가 k에게 지고 k가 b에게 지면 a가 b에게 지므로 graph[a][b] = -1 로 만들어준다.

4. 순위를 매길 수 있는 선수를 센다.

   4-1. graph[i][1:] 에 0이 하나이면 자기 자신을 제외하고 모든 노드에 승패 여부를 알 수 있다는 의미이므로 anwer에 +1을 한다.

 

 

다른 사람의 풀이를 찾아보니 이 문제는 여러 가지 방법이 있는 것 같다.

 

① DFS (스택)

def solution(n, results):
    chart = [[0] * n for _ in range(n)] # 승패표
    WIN, LOSE = 1, -1
    for i, j in results: # 내입장 wind = 상대방 lose
        chart[i-1][j-1], chart[j-1][i-1] = WIN, LOSE

    for me in range(n):
        wins = [opp for opp, rst in enumerate(chart[me]) if rst == WIN]
        while wins:
            loser = wins.pop()
            for opp, rst in enumerate(chart[loser]):
                if rst == WIN and chart[me][opp] == 0:
                    chart[me][opp], chart[opp][me] = WIN, LOSE
                    wins.append(opp)

    return len(['know' for x in chart if x.count(0) == 1])

 

② 딕셔너리

from collections import defaultdict

def solution(n, results):
    answer = 0
    wins = defaultdict(set)
    loses = defaultdict(set)

    for a, b in results:
        wins[a].add(b)
        loses[b].add(a)
    
    for i in range(1, n+1):
        for loser in wins[i]:
            loses[loser] |= loses[i]
        for winner in loses[i]:
            wins[winner] |= wins[i]

    for i in range(1, n+1):
        if len(wins[i]) + len(loses[i]) == n - 1:
            answer += 1

    return answer