#225

얽힌 그래프

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

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

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

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

문제 해결이 끝난 후 반드시 ‘제출’ 버튼을 눌러 제출해 주세요.
문제를 해결하려면 로그인해 주세요.

문제 형식

    인터랙티브

출처

  • KOI 2023 1차대회 초등부 1교시 13번
  • KOI 2023 1차대회 중등부 1교시 13번
연습하기도전하기함께하기보고 배우기
공지사항 · 이용안내
회원가입로그인
연습하기도전하기함께하기보고 배우기공지사항 · 이용안내