Question1 - [미들러] 순위
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/49191
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위입니다.
문제풀이
trial1 : BFS를 알고리즘 활용
A가 B에게, B가 C에게 졌는지 이겼는지 등을 확인할 선수들간 관계에 대한 자료들이 주어졌을 때,
정확하게 순위를 매길 수 있는 선수가 몇명인지를 반환해야 하는 문제이다.
이 경우 BFS는 너비 우선 탐색으로 서로 이겼는지 졌는지 여부를 모든 선수에 대해서 넓게 탐색한다는 것을 의미한다.
'정확하게 순위 매길 수 있는 선수'의 수는 '자기 자신을 제외하고 나머지 n-1 선수들과의 관계를 알 수 있는' 선수의 수와 같다.
따라서, 그 수를 구하기 위해서는 각 선수에 대해 BFS를 두 번 수행한다.
한 번은 자신이 이긴 선수 리스트를 담은 wins 그래프를, 다른 한 번은 자신이 진 선수 리스트를 담은 loses 그래프를 생성 및 탐색하여,
두 그래프에서 자기 자신을 제외하고 본인과의 승패 관계를 알 수 있는 선수의 개수가 n-1 인 경우를 반환한다.
아래 코드는 총 두 부분으로 나뉘어진다.
1) BFS 함수로 순회
- BFS를 사용하여 시작 노드(start)로부터 방문 가능한 모든 노드를 탐색하고, 그 노드들의 집합(visited)을 반환 한다.
2) Solution 함수 구현
- 이 함수는 선수의 수(n)와 경기 결과(results)를 입력으로 받아서, wins와 loses 그래프를 생성한 후 각 선수마다 BFS를 사용하여 이긴 선수들과 진 선수들의 수를 구한다. (이긴 선수 len 합 + 진 선수 len 합 - 자기 자신의 순위인 2)
- 그 결과가 n - 1과 같으면(count) 해당 선수의 순위가 확실하게 정해진 것으로 간주하고 count를 증가한다.
from collections import defaultdict, deque
def bfs(graph, start):
queue = deque([start])
visited = set([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
def solution(n, results):
wins = defaultdict(list)
loses = defaultdict(list)
for winner, loser in results:
wins[winner].append(loser)
loses[loser].append(winner)
# 각 선수가 몇 명의 선수와 승패가 결정되어 있는지 계산
count = 0
for player in range(1, n + 1):
total = len(bfs(wins, player)) + len(bfs(loses, player)) - 2 # 자기 자신 중복 제거
if total == n - 1:
count += 1
return count
trial2 : 플로이드-워셜 알고리즘 활용
플로이드 워셜 알고리즘이란,
모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘, 모든 쌍 최단 경로(All-Pairs Shortest Path)를 찾는 알고리즘이다.
이 알고리즘은 기본적으로 ‘거쳐가는 정점’을 기준으로 알고리즘을 수행하며, 모든 정점 쌍 사이의 최단 경로를 찾는 것을 목적으로 한다.
동적계획법에 의거한다. 또 음수 가중치의 엣지도 처리 가능하다.
아래 그림에서 보여주듯이, 이 알고리즘은 그래프의 가중치를 인접 행렬로 표현하여 각 정점 쌍 사이의 최단 경로를 계산한다.
플로이드-워셜 알고리즘의 시간 복잡도는 O(V^3)이며 V는 정점의 수를 의미한다.
모든 정점 쌍에 대해 최단 경로를 찾기 위해 세 개의 중첩된 반복문을 사용하기 때문에 세제곱의 복잡도가 발생, 따라서 V가 커짐에 따라 사용 여부를 조정해야 한다.
아래 문제 풀이에 플로이드-워셜 알고리즘을 적용해보면,
win_graph와 lose_graph는 각각 승리와 패배 관계를 저장하는 2차원 배열이며,
win_graph[i][j]가 True이면 i가 j를 이기는 경로가 있음을, lose_graph[i][j]가 True이면 i가 j에게 지는 경로가 있음을 의미한다.
이 matrix를 바탕으로 정확한 순위를 매길 수 있는 선수의 수를 count 변수에 세고,
각 선수에 대해 자신을 제외한 모든 선수와의 승패 관계가 결정된 경우, 즉 count가 n-1인 경우를 반환하여 문제를 푼다.
def solution(n, results):
# 승패 그래프 초기화
win_graph = [[False] * n for _ in range(n)]
lose_graph = [[False] * n for _ in range(n)]
# 결과를 그래프에 반영
for winner, loser in results:
win_graph[winner-1][loser-1] = True
lose_graph[loser-1][winner-1] = True
# 플로이드-워셜 알고리즘을 통해 간접 승패 관계 찾기
for k in range(n):
for i in range(n):
for j in range(n):
if win_graph[i][k] and win_graph[k][j]:
win_graph[i][j] = True
if lose_graph[i][k] and lose_graph[k][j]:
lose_graph[i][j] = True
# 정확한 순위를 매길 수 있는 선수 수 세기
answer = 0
for i in range(n):
count = 0
for j in range(n):
if win_graph[i][j] or lose_graph[i][j]:
count += 1
if count == n - 1: # 자신을 제외한 모든 선수와의 승패가 결정된 경우
answer += 1
return answer