2019번 - 다각형개수
문제 해설)
단 하나의 싸이클로만 존재하는 그래프를 찾는 문제입니다.
자신을 구성하는 싸이클 이외에 다른 엣지가 붙어있으면 안되므로, 다른 싸이클이 붙어있어도 안됩니다.
33%)
33% 언저리에서 막히는 경우는 자기 참조 엣지를 고려하지 않아서 입니다.문제의 어느 조건에도 x1 != x2, y1 != y2가 없기에, 이를 고려해야 합니다.
또한, 이 자기참조 엣지는 폴리곤을 구성하지 않기에, 이 엣지가 존재한다면, 카운트에 포함되지 않습니다.77%)중복되는 엣지도 존재할 수 있습니다.
예를 들어, (1, 1) -> (2, 2) 인 엣지가 2개 이상 존재할 수 있습니다.
또한, 폴리곤을 구성할 때, 하나의 엣지만 필요하므로 2개 이상 존재한다면 폴리곤을 구성하지 않는 엣지가 붙어있는 것입니다.
다음은 제가 사용한 예제들입니다. 이를 통과한다면 정답을 맞출 수 있을 것입니다.
+) 폴리곤을 구성하는 엣지들이 한 직선 위에 존재하는 경우도 하나의 폴리곤이라고 카운트하니, 이 부분은 고려하지 않아도 됩니다.
댓글을 작성하려면 로그인해야 합니다.
mystic6113 1년 전 1
문제 해설)
단 하나의 싸이클로만 존재하는 그래프를 찾는 문제입니다.
자신을 구성하는 싸이클 이외에 다른 엣지가 붙어있으면 안되므로, 다른 싸이클이 붙어있어도 안됩니다.
33%)
33% 언저리에서 막히는 경우는 자기 참조 엣지를 고려하지 않아서 입니다.
문제의 어느 조건에도 x1 != x2, y1 != y2가 없기에, 이를 고려해야 합니다.
또한, 이 자기참조 엣지는 폴리곤을 구성하지 않기에, 이 엣지가 존재한다면, 카운트에 포함되지 않습니다.
77%)
중복되는 엣지도 존재할 수 있습니다.
예를 들어, (1, 1) -> (2, 2) 인 엣지가 2개 이상 존재할 수 있습니다.
또한, 폴리곤을 구성할 때, 하나의 엣지만 필요하므로 2개 이상 존재한다면 폴리곤을 구성하지 않는 엣지가 붙어있는 것입니다.
다음은 제가 사용한 예제들입니다. 이를 통과한다면 정답을 맞출 수 있을 것입니다.
+) 폴리곤을 구성하는 엣지들이 한 직선 위에 존재하는 경우도 하나의 폴리곤이라고 카운트하니, 이 부분은 고려하지 않아도 됩니다.