[프로그래머스] Lv 3. 순위

코딩테스트 연습 - 순위

 

문제

심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다.

하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

 

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때

정확하게 순위를 매길 수 있는 선수위 수를 return 하도록 solution 함수를 작성해주세요.

 

풀이

A와 B라는 선수가 있을 때, A가 B에게 이겼다는 사실을 어떻게 알 수 있을까요?

바로 A에서 B로 가는 경로가 있을 때, A가 B에게 이겼다고 할 수 있습니다.

위의 이미지를 보시면 4번 선수는 2번 선수뿐만 아니라 5번 선수에게도 이긴다는 사실을 알 수 있습니다.

 

이제 다시 문제로 돌아와보겠습니다.

선수의 정확한 순위를 알기 위해서는 자신을 제외한 모든 선수에게 이기는지/지는지 알아야 합니다.

 

따라서 DFS(깊이우선탐색)을 이용해 A->B로 가는 경로가 있는지 탐색하고, 경로가 있다면

A는 B에게 이기고(1), B는 A에게 지는 것(-1)으로 처리하도록 하겠습니다.

결과 2차원 배열을 maps라 할 때, maps[A][B]가 1이면 A는 B에게 이긴다는 의미이며, maps[A][B]가 -1이면 A는 B에게 진다는 의미입니다.

따라서 A행의 모든 요소가 0이 아닌 1 또는 -1이면 A번 선수는 정확한 순위를 알 수 있습니다.😊👍

 

코드

class Solution {
    fun solution(n: Int, results: Array<IntArray>): Int {
        var answer = 0
        
        val graph = Array(n, { BooleanArray(n, {false}) })
        for (result in results) {
            val (s, e) = result
            graph[s-1][e-1] = true
        }
        
        val maps = Array(n, { IntArray(n, {0})})
        for (start in 0 until n) {
            val visited = BooleanArray(n, {false})
            maps[start][start] = 1
            dfs(start, start, graph, n, maps, visited)
        }
        
        for (player in 0 until n) {
            if (maps[player].contains(0).not()) {
                answer += 1
            }
        }
        return answer
    }
    
    fun dfs(start: Int, via: Int, graph: Array<BooleanArray>, n: Int, maps: Array<IntArray>, visited: BooleanArray) {
        visited[via] = true
        for (end in 0 until n) {
            if (graph[via][end] && visited[end].not()) {
                maps[start][end] = 1
                maps[end][start] = -1
                dfs(start, end, graph, n, maps, visited)
            }
        }
    }
}