[BOJ] 백준 25308 방사형 그래프 (Swift)

문제

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

25308번: 방사형 그래프

풀이

먼저, 순열을 통해 능력치를 나열할 수 있는 모든 경우를 구해줍시다.

이제 이 능력치에 대해서 a1, a2, a3가 볼록인지, a2, a3, a4가 볼록인지 ... a8, a1, a2가 모두 볼록인지 확인해주고
모두 볼록이라면 볼록 다각형이 만들어지는 경우일 것입니다.

다음과 같은 공식을 통해 볼록인지 확인할 수 있습니다.
$(a1 \times a3) \times \sqrt{2} \ge a2 \times (a1 + a3)$

1부터 8까지 모두 만족한다면 볼록 다각형이 만들어 지는 경우입니다.

소스코드

	import Foundation
	let array = readLine()!.split(separator: " ").map { Double($0)! }
	var permutationArrays: [[Double]] = []
	var visited = [Bool](repeating: false, count: 8)
	func dfs(n: Int, nums: [Double]) {
	if n == 8 {
	permutationArrays.append(nums)
	return
	}
	for i in 0..<8 {
	if !visited[i] {
	visited[i] = true
	dfs(n: n + 1, nums: nums + [array[i]])
	visited[i] = false
	}
	}
	}
	dfs(n: 0, nums: [])
	var answer = 0
	for arr in permutationArrays {
	var isSuccess = true
	for i in 0..<8 {
	if !(arr[i] * arr[(i + 2) % 8] * sqrt(2) <= arr[(i + 1) % 8] * (arr[i] + arr[(i + 2) % 8])) {
	isSuccess = false
	break
	}
	}
	answer += isSuccess ? 1 : 0
	}
	print(answer)

view raw 방사형 그래프.swift hosted with ❤ by GitHub

후기

이 블로그를 참고해서 풀었습니다.