[Swift Algorithm] 49191 순위 프로그래머스

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

코딩테스트 연습 - 순위

 

어떻게 구현해야할까 감이안오는 문제였어요..

처음에는

 

자신의 순위를 확실히하려면 n-1개의 정보가 필요함 을 이용해서 풀어보려고했어요

Set을 이용해서 이긴사람과 진사람을 체크한후

i를 이긴 사람은 i가 이긴사람을 다이김

i한테 진 사람은 i가 진사람한테 다짐

위의 로직을 적용해봤지만 일부 케이스만 통과하고

생각해보니

이긴사람, 진사람이 갱신되면 다시 업데이트 되야하는 그 과정이 누락된것같더라구요

 

이 논리로 푸려고했지만 계속실패해서 다른 방법을 찾아봤고

이방법이 정석인것 같았어요

 

 

플로이드 와샬

을 이용해서 푸는 문제라고 하더라구요?

 

다익스트라 - 하나의 정점에서 출발했을 때 모든 정점으로의 최단경로를 찾는 알고리즘

플로이드 와샬 - 모든 정점에서 모든정점으로 최단경로를 찾는 알고리즘

 

의 차이가 있구요

 

따라서 플로이드 와샬이란

현재 정점에서 모든 정점으로 부터의 최단거리를 구하는거에요

이게 왜 이문제에서 쓰이냐면

 

예시에

[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 가 입력으로 들어왔죠

 

4win 3lose  ->  4 3

4win 2lose  ->  4 (3,2)

3win 2lose  ->  4 3 2 

1win 2lose  ->   (4 1 3) 2 -> 4 1 3의 순서를 알 수 없어요

2win 5lose  ->  (4 1 3) 2 5 -> 4 1 3의 순서를 알 수 없어요 2,5는 확정

 

여기서 2와 5의 순위는 어떻게 아나요?

2가 4, 3, 1한테 지고 5한테 이겼어요

따라서 2는 4위가 확정이죠

 

5는 2한테 진거 뿐이에요

근데 꼴지가 됬어요

 

5는 2를 이긴 상대를 이길 수가 없죠!

 

이긴사람->진사람

방향그래프로 나타낸다면 4->2, 3->2, 1->2 인상태에서

2->5가 추가됬으니

4->5, 3->5, 1->5 도 만족하게 되는 그런 경로를 다 찾아보는거에요

 

모든 정점으로부터 자신의 경로를 찾는거죠

 

 

풀이방법

거리를 저장할 2차원 배열을 만들어주고

입력을 토대로 win -> lose를 만족하면 거리 1을 대입했어요

 

여기까진 기본적인 우승자를 알 수 있는 2차원배열이 완성됬어요

 

이 문제의 핵심인

플로이드 와샬을 적용시키고

[j][k]의 값과 [j][i] + [i][k]값을 비교해서 더 작은 값을 넣어주는 방식이에요

 

이 과정을 거치고나면

1이 2를 이겼다면 2가 이긴 상대를 모두 저장해논 상태일거에요

그래프에는 이긴사람의 정보만 넣었기때문이죠

 

배열을 비교할때

[i][j]의값과 [j][i]값을 비교하는데

1->2 인경우 값이 max값이아닐거고 2->1인경우에는 max가되기때문에 진경우는 값이 max가되요

따라서 두 값이 모두 max라면

한번도 경기를 해본적 없는 선수가 될거고

결국 순위를 알 수 없는 상태가 되겠죠

모든 선수와 경기를 해야 순위를 알 수 있기 때문이에요

 

private func solutionP49191(_ n:Int, _ results:[[Int]]) -> Int {
    let max = 9999999
    var node: [[Int]] = (0..<n).map { _ in [Int](repeating: max, count: n) }
    
    // win -> lose
    for result in results {
        node[result[0]-1][result[1]-1] = 1
    }
    
    func floyWashall() {
        for i in 0..<n {
            for j in 0..<n {
                for k in 0..<n {
                    node[j][k] = min(node[j][k], node[j][i] + node[i][k])
                }
            }
        }
    }
    floyWashall()
    
    var result = 0
    for i in 0..<n {
        var visit = true
        for j in 0..<n {
            //  자기자신인 경우 스킵
            if i == j {
                continue
            }
            
            // 방문한적 없는경우찾기
            // [i][j]과 [j][i]중 하나에만 값이 있는경우는 이기고 진과정에서 이긴경우만 저장했기때문
            if node[i][j] == max && node[j][i] == max {
                visit = false
                break
            }
        }
        
        if visit {
            result += 1
        }
    }
    
//    node.forEach { print($0) }
//    print(result)
    return result
}