[코테] 순위 Lv.3 (40%)

문제

###### 문제 설명

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

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

##### 제한사항

- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.

##### 입출력 예

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

##### 입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.  
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

문제 이해

2개의 딕셔너리를 만들어서, 선수를 key값으로하여 이긴 선수, 진 선수를 value로 담는다

말로 설명이 힘들기 때문에 위의 예를 들면,

win: {4: {2,3}, 3: {2}, 1:{2}, 2: {5}}

lose: {3: {4}, 2: {1,3,4}, 5: {2}}

win[4]에는 4번 선수가 이긴 선수가 담겨있고,

lose[3]에는 3번 선수가 진 선수가 담겨있다

 

딕셔너리가 생성됐으면, bfs를 통해 n번째 선수보다 상위의 선수는 bfs(win, n)를 통해 알 수 있고,

n번째 선수보다 하위의 선수는 bfs(lose,n)을 통해 알 수 있다

그럼 bfs(win,n)명   n번째 선수  bfs(lose,n)명 = n명이므로,

bfs(win,n) + bfs(lose,n) == n-1일 때 answer +=1 을 해주면 된다

 

 

풀이 💡

from collections import defaultdict

def solution(n, results):
    win = defaultdict(set)
    lose = defaultdict(set)
    for i in results:
        win[i[0]].add(i[1])
        lose[i[1]].add(i[0])
    answer = 0
    for i in range(1, n+1):
        if bfs(win ,i) + bfs(lose, i) == n-1:
            answer += 1
    return answer

def bfs(graph, start):
    queue = [[start, 0]]
    visited = []
    a = -1
    while queue:
        current = queue.pop(0)
        if current[0] not in visited:
            a += 1
            visited.append(current[0])
            if current[0] in graph:
                win = set(graph[current[0]]) - set(visited)
                queue.extend([[i, current[1]+1] for i in win])
    return a

 

 

 

n번 선수의 [최대 순위, 최소 순위] 리스트를 만드는 방식으로 풀었는데, 4위 선수에게 지면 5위가 되는 부분에서 막혔다

ex)  n =5 일 때,   [[1, 5], [1, 5], [1, 5], [1, 5], [1, 5]]  라는 전체 리스트를 만들어서 갱신 한 뒤, 최대 순위 = 최소 순위인 선수를 카운팅 하는 방식을 생각했다

 

다른 사람 풀이에서 플로이드 워셜을 이용한 풀이가 있었는데 이해하기 어렵고 사전 지식을 필요로 해서 bfs를 활용한 방식으로 학습하였다