순위 (python)

DFS 문제, 연쇄작용을 하는 유형

프로그래머스 문제 순위 - LV3

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

👀 깃헙 소스

문제설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

입출력 예

n	results						return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

솔루션

n*n 배열 chart를 만들어 각 지점에 경기결과를 저장해둔다.
ex) (1,0) = >1이 0과의 경기에서 얻은 결과
한 사람씩 반복문을 돌면서 이긴 경기에 대한 상대방을 wins에 저장해 둔다.
wins에서 진 사람들을 하나씩 pop하며 그들이 이긴 경기에대해 진 사람들을 다시 wins에 넣어주며 이를 반복한다.

chart 결과에서 1(win)이나 -1(lose)이 아닌 0으로 표현된것이 1개밖에 없다면(자기 자신과의 경기는 0) 순위를 알 수 있는 사람이고 이들의 명수를 반환해준다.

코드

방법 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])

방법 2) 해시(딕셔너리)사용

# wins
{4: {2, 3, 5}, 3: {2, 5}, 1: {2, 5}, 2: {5}, 5: set()}

# loses
{3: {4}, 2: {1, 3, 4}, 5: {1, 2, 3, 4}, 1: set(), 4: set()}

# 파이썬
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