[프로그래머스][플로이드-워셜] 순위

순위

프로그래머스

 

• 내 풀이
  • runners[i] = [나를 이긴 사람들, 내가 이긴 사람들] 형태로 저장.
  • 주어진 results로 직접 이긴/진 사람 등록.
  • 간접 관계 전파 (플로이드-워셜 방식)
    • A가 B에게 졌고 B가 C를 이겼으면 → A는 C에게도 짐
    • A가 B를 이겼고 B가 C에게 졌으면 → A는 C에게도 이김
    • 중복 방지를 위해 visited 배열 사용.
  • 정확한 순위 판별
    • 나를 이긴 사람 + 내가 이긴 사람 = n-1이면 순위 확정.

def solution(n, results):
    answer = 0
    runners=[[[] for _ in range(2)] for _ in range(n+1)]
    
    for win,lose in results:
        runners[win][1].append(lose)
        runners[lose][0].append(win)

    visited=[[False if i!=j else True for j in range(n+1)] for i in range(n+1)]
    for win, lose in runners:
        for w in win:
            for l in lose:
                if visited[w][l]:
                    continue
                visited[w][l]=True
                runners[w][1].append(l)
        for l in lose:
            for w in win:
                if visited[l][w]:
                    continue
                visited[l][w]=True
                runners[l][0].append(w)
            
    for win,lose in runners:
        if len(set(win+lose))>=n-1:
            answer+=1
    return answer

 

 

• 다른 사람 풀이
  • 플로이드-워셜 방식
    • i > k 이고 k > j 이면, i > j 이다
  • runners[i][j]:
    • 1: i가 j를 이김
    • -1: i가 j에게 짐
    • 0: 경기 결과 없음
  • win → 1, lose → -1 로 결과 저장
  • 간접 관계 전파 (플로이드-워셜 방식):
    • A > B, B > C → A > C
  • 나를 제외한 모든 선수와 관계(이김/짐)가 정해졌으면 순위 확정.

def solution(n, results):
    answer = 0
    runners = [[0] * n for _ in range(n)]  # runners[i][j] : i와 j의 관계 (1=이김, -1=짐)

    for win, lose in results:
        runners[win - 1][lose - 1] = 1
        runners[lose - 1][win - 1] = -1

    for mid in range(n):
        for src in range(n):
            for dst in range(n):
                if src == dst or runners[src][dst] != 0:
                    continue
                if runners[src][mid] == 1 and runners[mid][dst] == 1:
                    runners[src][dst] = 1
                    runners[dst][src] = -1

    for runner in runners:
        if runner.count(0) == 1:  # 자기 자신만 0인 경우
            answer += 1

    return answer