BOJ-2458 키 순서 Swift

문제

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서

표현하였다.

 

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.

다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 N보다 작거나 같은 서로 다른 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

내가 푼 풀이

접근방법: 플로이드-워셜 알고리즘

1. 예시 그래프처럼 비교한것을 그래프의 인접행렬로 담는다.

2. 플로이드-워셜 알고리즘을 이용한다면, 모든 노드쌍의 최단거리가 나온다.

3. 인접행렬 graph의 graph[i][j] 값의 의미는 i번이 j번보다 작다는 뜻이다, 반대로 graph[j][i]는 j는 i보다 작다는 의미다.

4. 본인을 제외한 나머지 인원이 작거나 큰 인원으로 알 수 있다면, 순서를 알 수 있다.

 

ex) 인접행렬에서 1번의 순서를 아는방법

garph[1][j]에 값이 있다면, 1번은 j보다 작다는 의미이고 값이 있는만큼 1번이 작다는 것이다.

graph[j][i]에 값이 있다면, 1번은 j보다 크다는 의미이고, 값이 있는만큼 1번이 크다는 것이다.

위의 두 값을 더해서 인원수-1 이라면, 순서를 알 수 있다!

 

인원수는 최대 500이라 플로이드-워셜알고리즘을 사용하면 1억2500만번 연산을 한다.

이 문제에서는 단순히 큰지 작은지 판단만 가능하면 되므로 bool값을 이용해 시간을 단축한다.

 

코드로 구현하면 다음과 같다.

 

import Foundation

// 입력
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], M = input[1]
var graph = Array(repeating: Array(repeating: false, count: N+1), count: N+1)
var answer = 0

// 그래프 입력
for i in 0..<M {
    let cp = readLine()!.split(separator: " ").map{Int(String($0))!}
    graph[cp[0]][cp[1]] = true
}
// 플로이드-워셜
// 단순히 자신보다 크거나 작은 인원이 있는지만 알기 위해 Bool값 이용(정수 이용하면 시간이 너무 오래걸린다.)
for m in 1...N {
    for i in 1...N {
        for j in 1...N {
            if graph[i][m] && graph[m][j] { graph[i][j] = true }
        }
    }
}

// 해당 번호보다 (더작은인원 + 더큰인원 = 본인제외한 인원수) 라면 순서를 알 수 있다.
for i in 1...N {
    var tall = 0
    var short = 0
    for j in 1...N {
        if i == j { continue }
        if graph[i][j] { tall += 1 }
        if graph[j][i] { short += 1 }
    }
    if tall+short == N-1 {
        answer += 1
    }
}

print(answer)