문제 설명

문제는 이 곳 링크를 참조하길 바란다.

• https://programmers.co.kr/learn/courses/30/lessons/49191

전체 코드

from collections import deque

def solution(n, results):
    def bfs(v, matrix):
        q = deque()
        q.append(v)
        visited = [0]*(n+1)
        visited[v] = 1
        temp = [v]

        while q:
            v = q.popleft()

            for i in matrix[v]:
                if visited[i] == 0:
                    q.append(i)
                    temp.append(i)
                    visited[i] = 1

        return temp

    matrix1 = [[] for _ in range(n+1)]
    matrix2 = [[] for _ in range(n+1)]

    for i in results:
        matrix1[i[1]].append(i[0])
        matrix2[i[0]].append(i[1])
    
    answer = 0
    for i in range(1, n+1):
        if len(set(bfs(i, matrix1) + bfs(i, matrix2))) == n:
            answer += 1

    return answer

해결 방법

기초적인 그래프 문제이다. 문제의 핵심은 입출력 예의 설명으로 "2번 선수는 [1,3,4]선수에게 패배했고 5번 선수에게 승리했기에 4위입니다."라는 말이다. 이 말은 2번을 탐색했을때 1,2,3,4,5가 모두 있다면 2번 선수의 순위를 구할 수 있다는 말이다. 따라서 matrix1은 이겼을때의 원소를 append하고 matrix2는 졌을때의 원소를 append해서 1 ~ n까지의 정점에 서 matrix1, matrix2에 대하여 bfs를 실행했을때 그 원소들의 길이의 합이 n과 같다면 순위를 매길수 있는 것이므로 answer에 +1을 해준다.