🛠 문제
👩🏻💻 해결 방법
문제 풀이를 참고해도 이해하기 어려웠던 문제였다...
우선 win, lose에는 각각 내가 이긴 선수, 나를 이긴 선수의 번호를 저장해주었다
따라서 win[i]안의 번호들은 loser가 되는 것이고, 이들은 lose[i]에 있는 번호들에게도 질 것이므로 lose[loser].update(lose[i])를 해주었다
반대로 lose[i]안의 번호들은 winner가 되는 것이고, 이들은 win[i]에 있는 번호들도 이길 것이므로 win[winner].update(win[i])를 해주었다
이후에 win과 lose의 길이 합이 n-1(자신 제외)이면 answer+1을 해주었다
다시 생각해도 이해하기 어려운 문제다...
소스 코드
def solution(n, results):
win, lose = {}, {}
for i in range(1, n + 1):
win[i], lose[i] = set(), set()
for i in range(1, n + 1):
for r in results:
if r[0] == i:
win[i].add(r[1])
if r[1] == i:
lose[i].add(r[0])
for winner in lose[i]:
win[winner].update(win[i])
for loser in win[i]:
lose[loser].update(lose[i])
answer = 0
for i in range(1, n + 1):
if len(win[i]) + len(lose[i]) == n - 1:
answer += 1
return answer💡 다른 사람의 풀이
def solution(n, results):
answer = 0
graph = [[0 for cols in range(n)] for rows in range(n)]
for r in results: #그래프 초기화
graph[r[0]-1][r[1]-1] = 1
graph[r[1]-1][r[0]-1] = -1
for i in range(n): #각 행별로 처리
for j in range(n):
if graph[i][j] == 1:
for m in range(n):
if graph[j][m] == 1 and graph[i][m] == 0:
graph[i][m] = 1
graph[m][i] = -1
elif graph[i][j] == -1:
for m in range(n):
if graph[j][m] == -1 and graph[i][m] == 0:
graph[i][m] = -1
graph[m][i] = 1
for i in range(n):
if graph[i].count(0) == 1:
answer += 1
return answer