[Swift] 백준골드4) 키 순서

https://www.acmicpc.net/problem/2458

1. 문제이해

• 키가 모두 다른 N명의 학생 중 자신의 키가 몇 번째인지 알 수 있는 학생의 수 구하기

2. 접근방법

X 노드에서 출발하거나, 다른 노드에서 X 노드에 도착하는 것이 모든 노드에 대해 가능할 때 자신의 키가 몇 번째인지 알 수 있는 학생이다.

플로이드 워셜

• 모든 지점에서 다른 모든 지점까지 최단 경로 구할 수 있음
• 이 문제는 거리를 구하는 것이 아닌 도달이 가능한지만 구하면 됨

자신의 키가 몇 번째인지 알 수 있는 학생 == 모든 노드에 접근 가능한 노드

3. 코드

func solution(){
    var input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let N = input[0]
    let M = input[1]
    var map = Array(repeating: Array(repeating: false, count: N), count: N)
    for _ in 0..<M{
        input = readLine()!.split(separator: " ").map{Int(String($0))!}
        map[input[0]-1][input[1]-1] = true
    }
    var result = N
    // 플로이드 워셜
    for z in 0..<N{
        for x in 0..<N{
            for y in 0..<N{
                if map[x][z] != false, map[z][y] != false{
                    map[x][y] = true
                }
            }
        }
    }

    // 자신의 키가 몇 번째인지 알 수 있는 학생
    func isComparable(cur: Int) -> Bool{
        var inputIndex = [Int]()
        for i in 0..<N{
            if cur != i, map[cur][i] == false{
                inputIndex.append(i)
            }
        }
        for i in inputIndex{
            if cur != i, map[i][cur] == false{
                return false
            }
        }
        return true
    }
    
    for i in 0..<N{
        if !isComparable(cur: i){
            result -= 1
        }
    }
    print(result)
}
solution()