[프로그래머스 파이썬] 순위

[프로그래머스 파이썬] 순위

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

프로그래머스

 

문제

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 

권투 경기는 1대 1 방식으로 진행, A 선수가 B 선수보다 실력이 좋다면

A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다.

하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수

 

각배열은 [A,B] results배열에 들어있다 A선수가 B선수를 이겼다는 의미이다 

입출력

풀이

나는 3개읠 배열을 만들었다

graph1 은 현재 번호대상으로 이긴 사람들을 집어넣었고

graph2은 현재 번호대상으로 진 사람을 집어넣었다

graph는 추후 답을  집어넣을 빈 배열을 n만큼 만들었다 

 

이문제를 순위를 구할필요가 없이 순위를 알 수 있는 사람만 수만 체크하면 되는데

이때 순서를 알 수 있게 하는 방법으로 나는 dfs방식을 사용하여 그래프를 탐색하였다 

현재 내가 k 이면 graph1 [k]는 k인 사람한테 이긴 사람들을 모아둔 걸로  배열로

이걸 탐색하여 날 이긴 사람을 알 수 있으며 날이긴 사람들에 대해서 날이긴 사람을 이긴 사람을 탐색하면

날 이긴 사람을 이긴 사람이기에 결국 날 이긴 사람이 된다 이 과정을 반복해서

최종적으로 날이긴 사람 모두를 체크할 수 있다 이렇게 탐색된 사람들은 graph에 넣었다

    def bfsup(i, k): 
        for j in graph1[i-1]:  #날이긴 사람들을 확인  
            if j not in graph[k-1]: #날이긴 사람들중 정답을 넣을 배열에 들어 있지 않다면 넣는다
                graph[k-1].append(j) 
                bfsup(j, k) #넣은 사람은 날 이긴 사람임으로 그 사람을 이긴 사람을 다시 탐색한다
                			#날이긴 사람을 이긴 사람또한 날 이긴 사람이기 이렇게 반복하게 되면
                            #graphp[k-1]에는 날이긴 사람들 전체가 들어오게 된다

반대로 나에게 진 사람을 탐색하는 것도 위와 똑같다 나에게 진사람을 돌고 그 진사람한테도 진 사람을 탐색하면

결국 최종적으로 맨 마지막에 탐색된 사람 또한 나에게 진 사람이 된다. 

    def bfsdown(i, k):
        for j in graph2[i-1]:
            if j not in graph[k-1]:
                graph[k-1].append(j)
                bfsdown(j, k)

 

이렇게 내 위에 있는 사람 모두 다 내 아래 있는 사람 모두들 탐색하면 된다

탐색이 끝나고 graph [k] n-1개의 수가 들어있으면 내 순위를 알 수 있는 사람임으로 이런 사람을 카운트하여

정답으로 출력하면 된다 

 

이 풀이 말고도 찾아보니 플로이드 워셜 풀이와 집합을 이용하여 dfs 풀이 방식을 좀 더 간다히 풀어쓴 풀이들이 있었다

3방식다 풀어보면서 플로이드 워셜은 생각을 좀 해야지만 이해가 되었다 

 

코드

dfs방식

def solution(n, results):
    answer = 0
    graph1 = [[] for _ in range(n)]
    graph2 = [[] for _ in range(n)]
    graph = [[] for _ in range(n)]

    for i in results:
        graph1[i[1]-1].append(i[0]) # 날이긴놈(패배)
        graph2[i[0]-1].append(i[1]) # 내가 이긴놈 (승리)

    def bfsup(i, k):
        for j in graph1[i-1]:
            if j not in graph[k-1]:
                graph[k-1].append(j)
                bfsup(j, k)

    def bfsdown(i, k):
        for j in graph2[i-1]:
            if j not in graph[k-1]:
                graph[k-1].append(j)
                bfsdown(j, k)

    for i in range(1, n+1):
        bfsup(i, i)
        bfsdown(i, i)

    for i in graph:
        if len(i) == n - 1:
            answer += 1

    return answer

플로이드워셜

def solution(n, results):
    answer = 0
    graph=[[-5 for x in range(n)] for j in range(n)]

    for x,y in results:
        graph[x-1][y-1]=1
        graph[y-1][x-1]=-1

    for i in range(n):
        graph[i][i]=0


    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k]==1 and graph[k][j]==1:
                    graph[i][j]=1
                elif graph[i][k]==-1 and graph[k][j]==-1:
                    graph[i][j]=-1

    for i in range(n):
        count=0
        for j in range(n):
            if graph[i][j]==1 or graph[i][j]==-1:
                count+=1
        if count==n-1:
            answer+=1

    return answer

집합을 이용한

def solution(n, results):
    answer = 0
    graph1=[[] for _ in range(n)]
    graph2=[[] for _ in range(n)]
    for i in results:
        graph1[i[1]-1].append(i[0]) #날이긴놈 
        graph2[i[0]-1].append(i[1]) #내가 이긴놈

    for i in range(n):
        for win in graph1[i]:
            graph2[win-1].extend(graph2[i])
        for lose in graph2[i]:
            graph1[lose-1].extend(graph1[i])
        
        graph1 = [list(set(lst)) for lst in graph1]
        graph2 = [list(set(lst)) for lst in graph2]

    for i in range(n):
        if len(graph1[i])+len(graph2[i])==n-1:
            answer+=1

    return answer