백준 18138번 리유나는 세일러복을 좋아해 - 스위프트(Swift) 풀이

---

 

1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다.
2. 티셔츠와 카라를 이분 매칭 한다.

 

1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다.

 티셔츠 집단과 카라 집단을 최대로 매칭 시켜야 하는 이분 매칭 문제이다. 먼저 각 티셔츠와 카라들을 그래프의 정점이라고 생각한 뒤, 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍을 간선으로 연결해 그래프를 만들어준다.

 

2. 티셔츠와 카라를 이분 매칭 한다.

 이제 완성된 그래프에 대해 이분 매칭을 진행하면 된다. DFS를 사용하여 구현하였다.

 

반응형

---

import Foundation

var N = 0, M = 0
var Tshirts = Array(repeating: 0, count: 201)
var collars = Array(repeating: 0, count: 201)
var owner = Array(repeating: -1, count: 201)    // owner[i] = i번째 카라와 매칭된 티셔츠 번호
var visit = Array(repeating: false, count: 201)
var adjacents = Array(repeating: [Int](), count: 201)

func DFS(_ index: Int) -> Bool {
    for adj in adjacents[index] {
        guard !visit[adj] else { continue }
        
        visit[adj] = true
        
        if owner[adj] == -1 || DFS(owner[adj]) {
            owner[adj] = index
            return true
        }
    }
    
    return false
}

func bipartiteMatch() -> Int {
    var count = 0
    
    for i in 0..<N {
        visit = Array(repeating: false, count: 201)
        if DFS(i) { count += 1 }
    }
    
    return count
}

func check(tShirt: Int, collar: Int) -> Bool {
    if (collar * 2 >= tShirt) && (collar * 4 <= tShirt * 3) { return true }
    else if (collar >= tShirt) && (collar * 4 <= tShirt * 5) { return true }
    else { return false }
}

func connectEdge() {
    for i in 0..<N {
        for j in 0..<M {
            if check(tShirt: Tshirts[i], collar: collars[j]) {
                adjacents[i].append(j)
            }
        }
    }
}

func solution() {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    M = input[1]
    
    for i in 0..<N { Tshirts[i] = Int(readLine()!)! }
    for i in 0..<M { collars[i] = Int(readLine()!)! }
    
    connectEdge()
    
    let result = bipartiteMatch()
    print(result)
}

solution()