얽힌 그래프

그래프란, 아래 그림과 같이 정점들과 간선들로 이루어져 있는 구조이다. 아래 그림에서 정점은 파란 색 원으로 표시되어 있다. 두 정점 사이를 잇고 있는 선을 간선이라고 한다.

평면 그래프란, 서로 교차하는 간선이 없는 그래프, 또는 정점을 적절히 옮겨서 그렇게 만들 수 있는 그래프를 뜻한다. 아래 그림의 그래프는 평면 그래프이지만, 현재 일부 간선이 교차하고 있다. 그림에서 교차하는 간선은 붉은색으로 표시되어 있고, 교차하는 간선들의 교차점에 노란색 원으로 표시되어 있다.

정점을 드래그해서 옮길 수 있다. 정점을 적절히 옮겨서 서로 교차하는 간선이 없도록 만들자.

제출 버튼을 눌렀을 때, 서로 교차하는 (붉은색으로 표시된) 간선이 존재하면 전체 점수의 0%를, 존재하지 않는다면 전체 점수의 100%를 받을 수 있다.

문제 형식

인터랙티브

출처

• KOI 2023 1차대회 초등부 1교시 13번
• KOI 2023 1차대회 중등부 1교시 13번