알고리즘
프로그래머스 Graph - 순위 (파이썬)
인공지능 대학생
2022. 5. 24. 14:01
Graph - 순위
* 프로그래밍 주안점
1. 가독성
2. 성능
문제링크: https://programmers.co.kr/learn/courses/30/lessons/49191
설명 (요약)
| 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다. 예: n results 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 결과: 2 |
풀이전략
- 모든 경우의 수에 대한 그래프가 있어야 한다.
- Start, End 가 없는 상태에서 모든 경우를 알아야 하기에 '플루이드워셜' 알고리즘을 적용
- 승패 그래프를 그렸을때 항목의 가로축, 세로축에 승패를 알수없는 항목이 하나도 없는 경우가 모든 승패를 아는 경우다.
고려사항
- 플루이드 워셜 그래프 만들기
코드
def solution(n, results):
# 1. 그래프 만들기
# 1.1. 자기자신 = None
# 1.2. 간선정보 입력
graph = [[0] * n for _ in range(n+1)]
#for a in range(1, n+1):
# graph[a][a] = None
for a, b in results:
graph[a-1][b-1] = 1 # Win
graph[b-1][a-1] = -1 # Lose; 0 = None
# 플루이드 워셜
for k in range(0, n):
for a in range(0, n):
for b in range(0, n):
# if graph[a][k] == None or graph[k][b] == None:
# continue
if graph[a][b] == 0:
if graph[a][k] == 1 and graph[k][b] == 1:
graph[a][b] = 1
elif graph[a][k] == -1 and graph[k][b] == -1:
graph[a][b] = -1
answer = 0
# 0(= None) 이 하나인 경우(자기자신)는 승패를 확실히 아는 경우
for i in range(0, n):
if graph[i].count(0) == 1:
answer += 1
return answer
solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]) # return 2
반응형