DFS 문제, 연쇄작용을 하는 유형
https://programmers.co.kr/learn/courses/30/lessons/49191
문제설명
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
입출력 예
n results return
5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
솔루션
n*n 배열 chart를 만들어 각 지점에 경기결과를 저장해둔다.
ex) (1,0) = >1이 0과의 경기에서 얻은 결과
한 사람씩 반복문을 돌면서 이긴 경기에 대한 상대방을 wins에 저장해 둔다.
wins에서 진 사람들을 하나씩 pop하며 그들이 이긴 경기에대해 진 사람들을 다시 wins에 넣어주며 이를 반복한다.
chart 결과에서 1(win)이나 -1(lose)이 아닌 0으로 표현된것이 1개밖에 없다면(자기 자신과의 경기는 0) 순위를 알 수 있는 사람이고 이들의 명수를 반환해준다.
코드
# 파이썬
def solution(n, results):
chart = [[0] * n for _ in range(n)] # 승패표
WIN, LOSE = 1, -1
for i, j in results: # 내입장 wind = 상대방 lose
chart[i-1][j-1], chart[j-1][i-1] = WIN, LOSE
for me in range(n):
wins = [opp for opp, rst in enumerate(chart[me]) if rst == WIN]
while wins:
loser = wins.pop()
for opp, rst in enumerate(chart[loser]):
if rst == WIN and chart[me][opp] == 0:
chart[me][opp], chart[opp][me] = WIN, LOSE
wins.append(opp)
return len(['know' for x in chart if x.count(0) == 1])
# wins
{4: {2, 3, 5}, 3: {2, 5}, 1: {2, 5}, 2: {5}, 5: set()}
# loses
{3: {4}, 2: {1, 3, 4}, 5: {1, 2, 3, 4}, 1: set(), 4: set()}
# 파이썬
from collections import defaultdict
def solution(n, results):
answer = 0
wins = defaultdict(set)
loses = defaultdict(set)
for a, b in results:
wins[a].add(b)
loses[b].add(a)
for i in range(1, n+1):
for loser in wins[i]:
loses[loser] |= loses[i]
for winner in loses[i]:
wins[winner] |= wins[i]
for i in range(1, n+1):
if len(wins[i]) + len(loses[i]) == n - 1:
answer += 1
return answer