lyzqm   3년 전

쥐가 해당 구멍에 들어갈 수있는지 판단검사 구현을 못하겠습니다.

1.png위와같은 그림이 있으면 M1,M2 쥐들은 H2구멍에 밖에 못들어갑니다.

제가 해보려고했던건 선분들을 가로,세로선분으로 나누고 정렬시키는 방식으로 처리하려했는데 

M2쥐와 같은 경우에서 처리가 잘 안될거같습니다.

팁좀주시면 감사하겠습니다

chogahui05   3년 전

교차점은 풀어보셨나요? 안 풀어보신 거 같은데 그거 먼저 풀어보시고 접근하시는 거 추천드려요.

이거 처리해야 할 케이스가 조금 있어요. 접근은 하셨다는 거 보니 쥐에서 홀까지의 선분은 그리실 생각은 하신 거 같고..


(1) 쥐 코너 벽 벽 벽 홀

아마 잘 생각하지 못하실 케이스인거 같긴 하네요.

이런 류의 케이스를 잘 분류해야 하는 게 교차점 문제입니다.


(2) 쥐 . . . . 홀 (이게 코너인 경우)


(3) 쥐 . . . . 코너 . . . . 홀

아마 m2 쥐와 같은 경우가 이 경우일 거 같은데요.

lyzqm   3년 전

감사합니다

추천문제 부터 풀고 다시한번 풀어보겠습니다 

chogahui05   3년 전

코너 케이스가 있는지라.. 무시는 못하긴 하네요..

선분 2개와 만날 때를 잘 처리해야 할 거 같네요. 3개 이상과 만나면 안 되는 건 자명한 사실이고..


2개와 만날 때

코너와 정확히 만나느냐와.. (#)


(그러니까 쥐 (코너 = 홀) 선분 선분 ,,,

                      선분

)

대충 이런 경우랄까요?


한 선분과 무한히 많은 교점이 있는가? 교차점 문제와 비교했을 때.. (#)이 추가가 되긴 했네요..

근데 교차점도 (#)은 따져줘야 하긴 하던데요.. 덜덜..

그러니까 홀이 코너에 딱 있는 경우에..


어짜피 선분 위에 Hall이 있기 때문에..

최소한 한 선분하고 만납니다.

lyzqm   3년 전

감사합니다.

교차점 먼저 풀고 코드 정리하고 다시푸니까 맞았네요 

추석 잘보내세요 ㅎㅎ

chogahui05   3년 전

거의 똑같은 문제였지요..? 이상하게 교차점 문제 냄새가 나서요..


중간에 이분 매칭만 조금 들어갔을 뿐인데.. 사실 그건 뭐.. 쥐구멍 1개당 3개, 4개, 5씩 만들어서

쥐랑 매칭시키면 될 거 같구요. 어려운 문제 하나 푸셨네요..


추석 잘 보내세요~

댓글을 작성하려면 로그인해야 합니다.