13. 얽힌 그래프 (10)
작성자
kangcoding
작성일
2024-05-19 17:59
조회
460
그래프란, 아래 그림과 같이 정점들과 간선들로 이루어져 있는 구조이다. 아래 그림에서 정점은 파란 색
원으로 표시되어 있다. 두 정점 사이를 잇고 있는 선을 간선이라고 한다.
평면 그래프란, 서로 교차하는 간선이 없는 그래프, 또는 정점을 적절히 옮겨서 그렇게 만들 수 있는 그래
프를 뜻한다. 아래 그림의 그래프는 평면 그래프이지만, 현재 일부 간선이 교차하고 있다. 그림에서 교차하는
간선은 붉은색으로 표시되어 있고, 교차하는 간선들의 교차점에 노란색 원으로 표시되어 있다.
정점을 드래그해서 옮길 수 있다.
정점을 적절히 옮겨서 서로 교차하는 간선이 없도록 만들자.
제출 버튼을 눌렀을 때, 서로 교차하는 (붉은색으로 표시된) 간선이 존재하면 전체 점수의 0%를, 존재하지
않는다면 전체 점수의 100%를 받을 수 있다
========== 풀이 ==========
겹친 빨간색 간선을 밖으로 빼내면 됩니다.
두 간선을 동시에 빼내기 위해서는 A를 오른쯕올 아주 멀리 빼내면 됩니다.
정답은 아래 그림과 같다.
전체 0