[그래프] 순위 - 프로그래머스
상하 관계만 보고 순위를 유추하는 유형. set 자료형을 이용하거나 플로이드-워셜 알고리즘을 응용하여 풀 수 있다.
문제 설명
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위입니다.
문제 풀이
간만에 그래프 문제에 접근하니 어떻게 풀어야 할지 접근 방법이 떠오르지 않았다. 추후 다시 풀면서 복기해야 할 것 같다.
문제의 핵심은,
- 어떤 팀에게 이기면 그 팀이 이긴 모든 팀보다 순위가 높고, 반대로 어떤 팀에게 지면 그 팀이 진 모든 팀보다 순위가 낮다
- 어떤 팀이 다른 모든 팀에게 지거나 이겼다면 그 팀의 순위가 정해진다
첫번째는 런닝맨 예능에서 이긴 사람이 진 사람의 이름표를 가진다고 하면 진 사람이 이때까지 이긴 모든 팀의 이름표를 이긴 사람에게 뺏기는 식으로 이해하면 된다.
따라서 이긴 사람은 진 사람의 이긴 전적을 모두 가져오고, 진 사람은 이긴 사람의 진 전적을 모두 가져온다. 여기에서 중복이 있으면 안되므로 set의 update 나 add 메서드를 사용할 수 있다.
이렇게 모두 업데이트한 경우 순위가 정해지려면 자신 이외의 모든 팀과 싸워 이기거나/진 전적이 존재하면 된다. n팀인 경우, n-1개의 승부가 존재하면 순위를 매길 수 있으므로 count한다.
풀이 방법은,
- set자료형 활용 또는
- 플로이드-워셜 알고리즘 으로 접근할 수 있다.
플로이드-워셜 알고리즘은 모든 경우의 최단거리를 구할 때 이용하는 알고리즘인데, 여기에서의 핵심은 A에서 B로 가는 최단거리는 모든 K에 대하여 (A-K-B 와 A-B 중 최솟값) 이다.
모든 노드끼리의 최단거리를 구하는 알고리즘이지만 이지만 이것을 A-B의 상하관계가 존재하지 않을 때 K를 이용하여 상하관계를 파악하는 것으로 응용할 수 있다.
A-K 가 ‘A가 K에게 이겼다’ 일때 거리 1이라고 하고, 반대로 졌을 때 -1이라고 하면 이면 A-K 와 K-B가 각각 1일 때 ‘A는 K에게 이기고, K는 B에게 이긴다’ 이므로 A-B는 확실히 ‘A는 B에게 이긴다’ 라고 말할 수 있다. 반대도 마찬가지다.
이것은 A-K * K-B가 1, 1 이거나 -1, -1 로 부호가 같을 때 성립하므로 거리값이 양수가 나올 때 상하관계가 존재하는 것이라 이야기할 수 있다.
중요: 플로이드 워셜 알고리즘에서 삼중 for 문의 순서는 K - A - B 여야 한다. 중간점인 K가 다른 순서로 간다면 로직이 꼬일 수 있다.
풀이 코드 - set 자료형 이용
def solution(n, results):
wins = [set() for _ in range(n+1)]
loses = [set() for _ in range(n+1)]
for w, l in results:
wins[w].add(l) # 어떤 팀을 이겼는지
loses[l].add(w) # 어떤 팀한테 졌는지
# 이기면 그동안 상대 팀이 이긴 전적 가져오고
# 지면 그동안 상대 팀이 진 전적 가져오기
# O(n^2)
for i in range(1, n+1):
for j in range(1, n+1):
if j in wins[i] or i in loses[j]: # i가 j 이김
wins[i].update(wins[j])
loses[j].update(loses[i])
elif i in wins[j] or j in loses[i]: # j가 i 이김
wins[j].update(wins[i])
loses[i].update(loses[j])
answer = 0
for k in range(1, n+1):
if len(wins[k]) + len(loses[k]) == n-1:
answer += 1
return answer
풀이 코드 - 플로이드 워셜 알고리즘
def solution(n, results):
board = [[0]*(n+1) for _ in range(n+1)]
for w, l in results:
board[w][l] = 1 # w가 l 이김
board[l][w] = -1 # l은 w한테 짐
# 플로이드 워셜 알고리즘 - k, a, b 순서 중요.
for k in range(1, n+1):
for x in range(1, n+1):
for y in range(1, n+1):
# 양수이면 관계 파악 가능, 음수 혹은 0이면 불가능
if board[x][k] * board[k][y] > 0: # 지고 지거나 이기고 이기면 확인됨
board[x][y] = board[x][k]
answer = 0
for i in range(1, n+1):
if board[i][1:].count(0) == 1:
answer += 1
return answer