순위

it 취업을 위한 알고리즘 문제 풀이

문제

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

[

코딩테스트 연습 - 순위

5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2

programmers.co.kr

](https://programmers.co.kr/learn/courses/30/lessons/49191)

코드

#https://programmers.co.kr/learn/courses/30/lessons/49191?language=python3

import sys 
from collections import deque
#sys.stdin = open("input.txt","rt")

cnt = 0
def DFS(graph, ch, vertex,flag,n):
    if ch[vertex] == 1:
        return

    ch[vertex] = 1
    global cnt
    if flag == 1:
        for i in range(1,n+1):
            if graph[vertex][i] == 1 and ch[i] != 1:
                cnt += 1
                DFS(graph,ch,i,flag,n)
    elif flag == -1:
        for i in range(1,n+1):
            if graph[vertex][i] == -1 and ch[i] != 1:
                cnt += 1
                DFS(graph,ch,i,flag,n)

    return 

def solution(n, results):
    answer = 0
    graph = [[0]*(n+1) for _ in range(n+1)]
    ch = [0]*(n+1)
    global cnt

    # 입력 값으로 그래프 만들기
    for result in results:
        graph[result[0]][result[1]] = 1
        graph[result[1]][result[0]] = -1

    for i in range(1,n+1):
        for j in range(1,n+1):
            ch[j]= 0
        cnt = 0
        # 승 수 계산
        DFS(graph,ch,i,1,n)

        for j in range(1,n+1):
            ch[j]= 0
        # 패 수 계산
        DFS(graph,ch,i,-1,n)

        # 승수와 패수를 모두 계산한
        if cnt == n-1:
            answer += 1

    return answer

문제해결방법

• 문제에서 '만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다.'라는 표현속에서 'A선수가 B선수를 이기고 B선수가 C선수를 이긴다면 A선수는 C선수를 이긴다.'라는 정보를 알수 있고 이를 바탕으로 그래프로 표현하기로 하였다. 그리고 이 그래프를 1번부터 5번을 모두 루트 노드로 하여 각각 모든 노드를 탐색 할 수 있다면 루트노드 번호에 해당하는 선수는 순위를 정할 수 있는 선수이다.
• 주어진 값에서 이길 수 있으면 1로, 지면 -1로 그래프의 정보를 표현하였고 그래프를 탐색하면서 방문가능한 노드의 개수를 체크하여 승수와 패수를 계산하여 승수와 패수를 합한 값이 n-1(n명이 출전하고 나를 제외한 모든 선수와 경기)과 같으면 순위를 정할 수 있으므로 answer 값을 1증가시켰다.