그래프 - 순위

이윤형·2021년 8월 10일

프로그래머스 코딩테스트 연습

목록 보기

4/5

1. 문제

문제 설명

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위입니다.

2. 풀이과정

그래프

우선 위의 예시에 대한 인접 리스트를 만들어보자. i에 대한 인접 리스트의 첫 번째 하위 리스트는 i가 이긴 상대, 두 번째 하위 리스트는 i가 진 상대이다.

i	adj[i][0]	adj[i][1]
1	[2]
2	[5]	[1,3,4]
3	[2]	[4]
4	[2,3]
5		[2]

이 때 순위를 확실히 하기 위해서는 직접 대결 뿐 아니라 "A > B 이고 B > C이면 A > C이다" 와 같은 간접 대결에 대한 결과도 업데이트 해야 한다. 예를 들어 i=1 일 때, 1은 2를 이겼다. 따라서 2가 이긴 모든 상대 j에 대해 adj[j][0]을 업데이트(1을 추가)해줘야 하며, 1이 진 모든 상대 j에 대해 adj[j][1]을 업데이트(2를 추가) 해줘야 한다. 여기서 중요한 것은 이 업데이트 과정을 하는 순서는 중요하지 않으며, 업데이트 과정은 한 번만 거치면 된다는 것이다.
예를 들어, i=1에 대해 업데이트를 먼저 진행 후 i=2에 대해 업데이트를 진행하면 인접 리스트는

i=1 에 대해 업데이트
i | adj[i][0] | adj[i][1]
|-|-|-|
1 | [2] |
2 | [5] | [1,3,4]
3 | [2] | [4]
4 | [2,3] |
5 | | [2, 1]

i=2 에 대해 업데이트(변화 없음)
i | adj[i][0] | adj[i][1]
|-|-|-|
1 | [2] |
2 | [5] | [1,3,4]
3 | [2] | [4]
4 | [2,3] |
5 | | [2, 1]

와 같이 변한다.

만약 i=2에 대해 업데이트를 먼저 진행 후 i=1에 대해 업데이트를 진행하면 인접 리스트는

i=2 에 대해 업데이트(변화 없음)
i | adj[i][0] | adj[i][1]
|-|-|-|
1 | [2] |
2 | [5] | [1,3,4]
3 | [2] | [4]
4 | [2,3] |
5 | | [2]

i=1 에 대해 업데이트
i | adj[i][0] | adj[i][1]
|-|-|-|
1 | [2] |
2 | [5] | [1,3,4]
3 | [2] | [4]
4 | [2,3] |
5 | | [2, 1]

로 변하므로 업데이트의 순서를 바꾸어도 결과는 같다. 따라서 업데이트 진행 시 i=1부터 차례대로 업데이트를 진행해도 무방하다.

코드

def solution(n, results):
    from collections import deque
    import copy
        
    ## 인접리스트 정의
    adj = [[set(),set()] for i in range(n+1)] 
    
    ## 인접리스트 채우기: i번째 리스트의 첫번째 set은 i가 이긴 목록, 두번째 set은 i가 진 목록
    for r in results:
        v = r[0]
        l = r[1]
        adj[v][0].add(l)
        adj[l][1].add(v)
        
    ## 직접순위 정해진 pair의 list 생성
    visited = copy.copy(results)
    
    def order_dec(v, adj, visited): ## 간접 순위를 가리는 함수
        for loser in adj[v][0]:
            adj[loser][1].update(adj[v][1])
        for winner in adj[v][1]:
            adj[winner][0].update(adj[v][0])
    
    for v in range(1, n+1):
        order_dec(v, adj, visited)
    
    decided = [len(adj[i][0])+len(adj[i][1]) == n-1 for i in range(len(adj))]
    answer = sum(decided)
    return answer