[프로그래머스 - 순위] [그래프][DFS]

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

코딩테스트 연습 - 순위

 

해당 문제에 대한 풀이를 검색한 결과 

플로이드 와샬 알고리즘을 활용한 풀이가 많았지만, 

 

실전에서 과연 플로이드 와샬 알고리즘을 활용할수있을까? 라는 의문이 더 앞선 문제였다. 

그래서 조금은 흔한 방법인 DFS 를 활용한 풀이를 게시할려 한다. 

 

풀이방법 

1. 권투 대회에서 이기는 방향, 지는 방향으로 Dictionary 배열 생성 총 두개를 생성한다.

프로그래머스 예제 데이터

권투에서 이기는 방향으로 화살표로 표현했을시 

다음과 같이 Dictionary 두개를 생성할수있다. 

 

Dict = { 1:[2] , 3:[2] ,4:[2],2:[5] }
Dict = { 2:[1,3,4] , 5:[2] }

 

 

2. 1~n 까지 돌면서 이기는 방향 , 지는 방향으로 dfs 탐색을 하며 visit 배열 체크를 한다. 

3. 1~n 까지 visit 배열의 합이 n 일시 answer 값에다가 +1 을 해준다. 

 

visit = [0] * 200


def get_dfs(now, node_dict):
    global visit
    visit[now] = 1

    for val in node_dict[now]:
        if visit[val] != 1:
            get_dfs(val, node_dict)


def solution(n, results):
    global visit
    answer = 0

    front_dict = {}
    back_dict = {}

    for i in range(1, n+1):
        front_dict[i] = []
        back_dict[i] = []

    for result in results:
        front_dict[result[0]].append(result[1])
        back_dict[result[1]].append(result[0])

    for i in range(1, n+1):
        visit = [0] * 200
        get_dfs(i, front_dict)
        get_dfs(i, back_dict)

        if sum(visit) == n:
            answer += 1

    return answer

print(solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]))