백준 - 공항(Swift)

백준 - 공항(Swift)

 

 

 문제 설명

 

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

10775번: 공항

 

 

 나의 풀이

 

상당히 어려웠던 문제다.

처음 접근은 비행기가 도킹할 수 있는 게이트가 주어졌을때 가장 큰 부분을 배치하면 된다라는 아이디어였다.

하지만 방문처리하는 부분이 애매했다. 예를들어 1~6까지의 게이트가 있고 3개의 비행기가 갈수있는 게이트가 6 6 6으로 주어졌다면

처음 6에 대한 부분은 false로해서 만들 수 있지만 6이 아닐때 6-1 을 한 5로 넣고, 또 5가 false일때 5-1을 넣어서 재귀적으로 호출하는 방법이 있는데, 이는 많은 시간복잡도를 내놓게 된다.

 

결국 다른사람의 풀이를 참고해서 재귀를 최소한으로 줄이는 방법을 찾았다.

 

첫번째 핵심은 동일하다.

주어진 게이트 중에서 가장 큰 게이트를 배치하자.

 

먼저 parents라는 배열을 각각 0~Gate의 개수까지 초기화를 한 뒤 도킹이 가능 한 경우를 0번 게이트까지 가지않은 경우로 두고 도킹이 불가능한 경우를 0번 게이트에 도달한 경우로 두었다.

 

그리고 한 번 도킹을한다면 parents[node]값을 1감소함으로써 해당 번호게이트에서는 도킹이 불가한 형태로 두었다.(해당 게이트가 도킹이 불가한 것이지 그전 게이트는 도킹이 가능한 상태)

 

정리하자면

각 비행기의 게이트번호에 대해서 root값을 구하는 데 root값이 0이라면 비행기를 도킹할 수 없는 상태이기 때문에 끝인 것이다.

 

 

 

 

import Foundation

let G = Int(readLine()!)!
let P = Int(readLine()!)!

var parents = [Int]()
var gates = [Int]()
var total = 0
for i in 0..<G+1 {
    parents.append(i)
}

for _ in 0..<P {
    let gate = Int(readLine()!)!
    gates.append(gate)
}

for gate in gates {
    let root = find(gate)
    if root == 0 { // 도킹할 게이트가 존재하지 않을경우
        break
    }
    parents[root] -= 1 // 도킹한 곳은 -1을 해서 나중에 다시 게이트에 접근하려고할 때 한 칸옆으로 이동하게 끔 한다.
    total += 1
}

print(total)

func find(_ node: Int) -> Int {
    if node == parents[node] { // 도킹이 아직 안되어있다면 
        return node
    } else {
        parents[node] = find(parents[node]) // 한 번 깊게 탐색한 값을 설정함으로써 시간복잡도를 줄임.
        return parents[node]
    }
}