프로그래머스 Level 3 순위

순위

출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

 

코드 

class Solution {
    fun solution(n: Int, results: Array<IntArray>): Int {
        var answer = n
        val graph = Array<Array<Int?>>(n){ arrayOfNulls(n) }
        results.forEach { (n1, n2) ->
            graph[n1-1][n2-1] = 1
            graph[n2-1][n1-1] = -1
        }
        for(i in 0 until n) {
            graph[i][i] = 0
        }
        for(k in 0 until n) {
            for(i in 0 until n) {
                for(j in 0 until n) {
                    if(graph[i][k] == 1 && graph[k][j] == 1) {
                        graph[i][j] = 1
                        graph[j][i] = -1
                    }
                }
            }
        }
        graph.forEach {
            if(it.contains(null)) answer--
        }
        return answer
    }
}

 

제가 어떻게 문제를 풀었는지 과정을 말씀드리겠습니다. 

 

처음에 먼저 각 노드가 이길 수 있는 노드들을 한 번 적어봤었습니다.

4는 3과 2를 이기고

3은 2를 이기고

1은 2를 이기고

2는 5를 이기고

 

이 정보를 가지고 순위를 정할 수 있을까 고민해 보니 이기는 정보만으로는 안 되겠다 생각했습니다.

그래서 내가 지는 경우도 적어보자 했고 그래서 자연스럽게 리스트가 아닌 배열로 생각을 전환하게 되었습니다.

 

먼저 정보를 담을 그래프를 배열로 만들어줍니다.

그리고 자기 자신은 0으로 초기화합니다.

val graph = Array<Array<Int?>>(n){ arrayOfNulls(n) }

for(i in 0 until n) {
    graph[i][i] = 0
}

 

현재 배열의 상태는 아래와 같습니다.

n은 null을 의미합니다. 처음에 배열을 선언할 때 null로 초기화된 배열을 만들어주어서 

이제 result 배열의 정보를 graph에 담아줍니다.

 

results.forEach { (n1, n2) ->
    graph[n1-1][n2-1] = 1
    graph[n2-1][n1-1] = -1
}

 

첫 번째 [4,3]을 보시면 4는 3을 이기기 때문에 4행 3열에 1을 넣습니다.

반대로 생각하면 3은 4에게 지기 때문에 3행 4열에는 -1을 넣습니다. 

1로 이기는 표현을 -1로 지는 표현을 만들어줍니다.

이렇게 모든 노드를 정리하면 아래처럼 됩니다.

 

 

이제 각 노드들이 이기는 노드를 보고 내가 이길 수 있는 노드가 누구를 이기는지 봅니다

무슨 말이냐!!

1번은 2번을 이깁니다. 

2번은 5번을 이깁니다.

그럼 1번은 5번도 무조건 이길 수 있습니다. 

1번 권투 선수는 2번을 무조건 이기므로 2번보다 약한 5번은 1번에게도 무조건 지게 됩니다.

이렇게 모든 노드를 갱신해 줍니다.

 

이때 삼중 for문을 이용해 각 노드들을 갱신하게 되는데 

for(k in 0 until n) {
    for(i in 0 until n) {
        for(j in 0 until n) {
            if(graph[i][k] == 1 && graph[k][j] == 1) {
                graph[i][j] = 1
                graph[j][i] = -1
            }
        }
    }
}

이때 구조가 플로이드 워셜 알고리즘과 과정이 흡사하게 진행되기 때문에 플로이드 워셜 알고리즘을 알고 계셨다면

문제 풀이의 핵심을 금방 눈치챌 수 있습니다.

혹시 플로이드 와샬 알고리즘이 궁금하시면 아래에 링크 확인하시면 됩니다.

2023.03.05 - [알고리즘] - 플로이드 와샬 ( Floyd Warshall ) 알고리즘 - (Kotlin)

플로이드 와샬 ( Floyd Warshall ) 알고리즘 - (Kotlin)

 

그래서 다시 코드를 보면

가장 밖의 반복문 k는 내가 이기는 노드를 확인하기 위한 중간 지점을 나타냅니다.

if문을 보면 graph [i][k]가 1일 때를 확인하는데 이거는 i번째 노드가 k번째에서 이기냐 (1 이냐)를 봅니다.

1번 노드는 1번 노드부터 가면서 확인합니다.

1번 노드가 이길 수 있는 노드 2번 노드가 되었을 때 graph [1][2] = 1을 만족합니다.

이제 1번이 이기는 2번에서 2번이 이기는 노드를 확인합니다.

2번을 1번 노드부터 확인합니다.

2번은 5번 노드를 이깁니다.

그럼 graph [2][5] = 1을 만족합니다. 

이때 1번은 2번을 이기고 2번은 5번을 이기게 되어

i = 1 , k = 2 , j = 5가 되고

graph [1][5] = 1로 갱신하고 반대로 5번은 무조건 1번에게 지게 되어 graph [5][1]=-1로 갱신합니다.

 

이해가 되시나요???

 

결국 모든 노드에서 내가 이기고 그 이기는 노드가 이기는 노드를 찾아내서 모든 경우를 갱신합니다.

갱신된 그래프 배열은 아래와 같습니다.

그런데 아직 n인 곳이 남아있네요??

이게 뭘 의미하냐 

이곳은 순위를 정할 수 없는 곳 즉 정보가 부족한 곳을 의미합니다.

이걸 보고 1번은 순위를 정할 수 있냐 없냐를 판단할 수 있습니다.

2번 노드는 전부 값을 가지고 있습니다. 

이건 순위를 정할 수 있습니다. 

그렇다면

각 노드의 배열에 null이 있는지 없는지를 확인하면 그 노드가 모든 경우가 나와서 순위를 정할 수 있는 친구인지 아닌지 알 수 있게 됩니다. 

graph.forEach {
    if(it.contains(null)) answer--
}

그래서 it.contain(null)이면 전체 개수에서 하나를 뺍니다.

반대로 !it.contain(null)를 써서  null이 없다면 answer++로 찾아도 되겠습니다.

 

이상으로 순위 문제를 플로이드 와샬을 응요하여 풀어보는 시간이었습니다.

읽어주셔서 감사합니다.