Swift ) 프로그래머스(Lv3) - 순위 (BFS / Floyd-Warshall)

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

코딩테스트 연습 - 순위

안녕하세요 후르륵짭짭 입니다.

이번에는 프로그래머스의 순위라는 문제를 들고 왔습니다.

저는 이 문제를 쫌 고민 했었는데, 결국 한시간 쫌 넘게 해서 풀었습니다 ㅠㅠ

생각하는데 쫌 걸렸는데,,, 알고리즘을 생각하는 능력이 정말 어떻게 해야 늘지 ㅠㅠ

 

일단 저는 BFS로 풀었는데, 플로이드 워셜로 풀 수 있는 것을 알고 놀랐습니다.

그럼 설명 하도록 하겠습니다.

 

** BFS 풀이 방법 ** 

처음에는 어떻게 풀어야 할지 고민을 했습니다.

그런데 1번 예시를 보니 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 이런 상황일 때, 2와 5가 순위를 매길 수 있는 경우가 되어 2가 정답이였습니다.

그래서 더 생각해보니, 순위를 출력할 필요가 없으니, 모든 경우가 연결 되어 있으면 순위를 매길 수 있구나 라고 생각했습니다.

2 보다 강한 팀은 1,3,4 입니다. 그리고 2보다 약한 팀은 5 입니다.

5 보다 강한 팀은 2 입니다. 그리고 5 보다 약한 팀은 없습니다.

따라서 2는 주어진 것으로 모두 연결 되어 있음을 확인 할 수 있고

5는 2가 1,3,4 랑 연결 되어 있으니, 덩달아서 전부가 연결 된 것을 확인 할 수 있습니다.

따라서 승리와 패배의 길을 만들어서 모든 경로를 탐색해줄 필요가 있습니다.

var winDict : [Int : [Int] ] = [:]
var lossDict : [Int : [Int] ] = [:]

func solution(_ n:Int, _ results:[[Int]]) -> Int {

    var answer = 0
    
    for connect in results{
        winDict[connect[0] , default : []].append(connect[1])
        lossDict[connect[1], default : []].append(connect[0])
    }
    
    for node in 1...n{
        
        var visited : [Bool] = Array(repeating: true, count: n+1)
        
        winBFS(&visited, node)
        lossBFS(&visited, node)
        
        visited.removeFirst()
        
        let count = visited.filter { (ele) -> Bool in
            return ele
        }.count
        
        print("\(node) \(count) : \(visited)")
        
        if count == 0 {
            answer += 1
        }
        
    }
    
    return answer
}

func lossBFS(_ visited : inout [Bool], _ node : Int){
    
    visited[node] = false
    var queue : [Int] = [node]
    
    while !queue.isEmpty{
        
        let node = queue.removeLast()
        
        for child in lossDict[node , default: []] {
            
            if visited[child] {
                
                visited[child] = false
                queue.insert(child, at: 0)
                
            }
            
        }
        
    }
    
}

func winBFS(_ visited : inout [Bool], _ node : Int){
    
    visited[node] = false
    var queue : [Int] = [node]
    
    while !queue.isEmpty{
        
        let node = queue.removeLast()
        
        for child in winDict[node , default: []] {
            
            if visited[child] {
                
                visited[child] = false
                queue.insert(child, at: 0)
                
            }
            
        }
        
    }
    
}

그래서 위의 코드 처럼 LoosBFS와 WinBFS를 두번 돌려주면 완전 탐색이 되는 겁니다.

딕셔너리로 연결성을 만들어주고 모든 노드에 대해서 WinBFS랑 LoosBFS를 돌려줘서 

전체 탐색을 해주면 끝입니다!!

 

** 플로이드 워셜 **

저는 이 방법으로 풀지 못했지만 개인적으로 공부가 되서 좋았습니다.

이런 방법을 생각하지도 못 했습니다 ㅎㅎㅎ

hururuek-chapchap.tistory.com/113

Swift ) LeetCode(Medium) - Find the City With the Smallest Number of Neighbors at a Threshold Distance (Floyd - Warshall)

이전에 플로이드 워셜에 대해서 다뤄 본적이 있는데 프로그래머스에서는 처음 인 것 같습니다 ㅎㅎㅎ

(Young-Jun Gu 님의 알고리즘 입니다.)

func solution(_ n:Int, _ results:[[Int]]) -> Int {
    let INF: Int = 987654321
    var answer = 0
    var matrix: [[Int]] = [[Int]](repeating: [Int](repeating: INF, count: n), count: n)

    for i in 0..<n {
        matrix[i][i] = 0
    }

    results.forEach{ result in
        matrix[result.first! - 1][result.last! - 1] = 1
    }

    for a in 0..<n {
        for i in 0..<n {
            for j in 0..<n {
                matrix[i][j] = min(matrix[i][j], matrix[i][a] + matrix[a][j])
            }
        }
    }
    // 플로이드-와샬 알고리즘
    var flag = [Bool](repeating: true, count: n)
    for i in 0..<n {
        for j in 0..<n {
            if i == j { continue }
            if matrix[i][j] == INF {
                if matrix[j][i] == INF {
                    flag[i] = false
                    break
                }
            }
        }
    }

    flag.forEach{ if $0 { answer += 1 } }

    return answer
}

저의 코드 보다 훨씬 짧고 좋습니다 ㅎㅎㅎ

일단 매트릭스를 만들어 줍니다. 그리고 입력 값에서 [강한쪽][약한쪽] = 1 로 설정해주면서 초기값을 줍니다.

그리고  [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 같은 상황 일 때, 플로이드 워셜 알고리즘을 사용해줍니다.

위의 그림 처럼 4 - 5 는 4 - 2 - 5 로 연결 되어 있기 때문에 무한대랑 2랑 비교해서 4 - 2 - 5 는 연결되어 있다를 표시해줍니다.

이렇게 해주면 전체 승리의 관계를 만들 수 있게 됩니다. 아래 그림 처럼,,,,

var flag = [Bool](repeating: true, count: n)
    for i in 0..<n {
        for j in 0..<n {
            if i == j { continue }
            if matrix[i][j] == INF {
                if matrix[j][i] == INF {
                    flag[i] = false
                    break
                }
            }
        }
    }

그리고 이제 위 알고리즘을 이용해서 승패 관계가 모두 연결 되어 있지 않을 때, 모든 노드가 연결이 되어 있지 않아서

승패 여부를 따질 수 없게 됩니다.

예를 들어 5 -> 1 은 무한대라서 승의 관계가 안되지만 1 -> 5 는 승의 관계 이기 때문에 5가 1 보다 밑 순위라는 것을 알 수 있습니다.

반면 1 -> 3 은 무한대라서 승의 관계가 안되는데, 3 -> 1 도 무한대라서 승의 승관계를 알 수 없기 때문에, 밑 순위인지 윗 순위 인지 알 수 없게 됩니다.

 

여기 까지 이해 했으면 저의 알고리즘과 Young-Jun Gu의 알고리즘 모두 이해한 것 입니다.

사실,,, 아직 어떻게 플로이드 워셜을 잘 사용 할 수 있을지 감이 잘 안 잡힙니다 ㅠㅠ

더 풀어봐야 할 것 같습니다 ㅠㅠ