경로 세기

시작 정점 S(파란색)와 끝 정점 E(주황색), 그리고 S에서 E로 향하는 간선 하나로 이루어진 방향 그래프가 주어진다. 현재 S에서 E로 가는 경로는 1개이다.

여러분은 새로운 정점을 추가하거나 정점 사이에 간선을 그어서 그래프를 확장할 수 있다. 단, 그래프에 사이클이 생기면 안 된다.

화면 상단에 S에서 E까지의 현재 경로 수가 큰 숫자로 표시된다. 목표를 달성하면 초록색으로 바뀐다. 정점은 원으로 표시된다. 시작 정점 S는 파란색, 끝 정점 E는 주황색, 추가된 정점은 흰색이다. 간선은 화살표로 표시되며, 방향을 나타낸다. S→E 간선은 삭제할 수 없다.

조작 방법

• 간선 생성: 정점을 클릭하여 선택한 뒤, 다른 정점을 클릭하면 첫 번째 정점에서 두 번째 정점으로 향하는 간선이 만들어진다.
• 간선 삭제: 이미 존재하는 간선 위에서 같은 조작을 하거나, 간선을 직접 클릭하면 삭제된다. S→E 간선은 삭제할 수 없다.
• 정점 추가: 하단의 + 버튼을 클릭하면 새 정점이 추가된다. 정점은 최대 20개까지 추가할 수 있다.
• 정점 삭제: S와 E를 제외한 정점을 휴지통 아이콘으로 드래그하면 삭제된다.
• 정점 이동: 정점을 드래그하여 위치를 조정할 수 있다.

목표

S에서 E까지의 서로 다른 경로 수가 정확히 이 되도록 그래프를 구성하는 것이다.

제약 조건

그래프에는 사이클이 있으면 안 된다. 간선을 생성할 때 사이클이 생기는 경우, 생성할 수 없다.

채점 기준

S에서 E까지의 경로 수가 정확히 이면 전체 점수를 받는다.

문제 형식

인터랙티브

출처

• KOI 2026 1차대회 초등부 1교시 20번