[Python] 백준 - 25308 방사형 그래프

<백준 25308 방사형그래프 문제 페이지 링크>

 

 

문제해결방법 - (구글링, 챗GPT 참조)

 

1. 신발끈 공식이라 일컬어지는 사선공식을 활용한다. 이 사선공식은 좌표로 주어지는 삼각형의 넓이를 구하는 공식인데, 절댓값을 취하기 전, 계산한 결과가 음수냐 양수냐에 따라 p1(x1, y1), p2(x2, y2), p3(x3, y3)의 순서로 선을 긋는다고 할 때 시계방향인지, 반시계방향인지 알 수 있다. (음수면 시계방향, 양수면 반시계방향)

 

이 문제에서 방향을 체크하는 것으로 연동되어 알 수 있는 것은 삼각형이 p2(x2, y2)에 따라 볼록하냐, 오목하냐를 알 수 있다는 것이다. 

 

 

위 그림을 보면 쉽게 알 수 있다. 이제 팔각형을 x-y축의 직각 좌표계로 바꾸어서 각각의 요소마다 삼각형을 판단할 수 있어야 한다. 정중앙을 (0, 0)이라고 할 때, p2의 좌표값(x2, y2)은 피타고라스의 정리를 활용하여 구할 수 있다.

 

2. 그리고 능력치의 배열은 순열로 8!(40320가지)의 경우의 수대로 배열을 바꾸어서 저장하여 볼록인 경우만 True로 판단하여 8가지 능력치가 전부 True일 때, 카운트를 증가시키면 된다.

 

- 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

p = list(map(int, input().split()))
v = [0 for _ in range(8)]
pmt, res = [], []

def dfs(idx):
	if idx == 8:
		pmt.append(res[:])
		return
	for next in range(8):
		if v[next] == 0:
			v[next] = 1
			res.append(p[next])
			dfs(idx+1)
			res.pop()
			v[next] = 0
dfs(0)

def ccw(a, b, c):
	x1, y1 = 0, a
	x2, y2 = ((b**2)/2)**0.5, ((b**2)/2)**0.5
	x3, y3 = c, 0
	l = (x1*y2+x2*y3+x3*y1)
	r = (x2*y1+x3*y2+x1*y3)
	temp = l-r
	if temp <= 0:
		return True
	return False
		
def checker(pmt):
	cnt = 0
	for idx in range(len(pmt)):
		flag = True
		for i in range(8):
			if not ccw(pmt[idx][i], pmt[idx][(i+1)%8], pmt[idx][(i+2)%8]):
				flag = False
				break
		if flag:
			cnt += 1
	return cnt

print(checker(pmt))