아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Python 클래스

시간 제한2초메모리 제한512 MB

요약
상위 클래스가 하위 클래스보다 앞에 오도록 클래스 정의 순서를 재배치할 때, 잘라서 붙이는 이동 최소 횟수를 구합니다. 상속 관계에 순환이 있으면 -1을 출력합니다.
난이도

어려움10점 중 8점

유형
그리디, 유니온 파인드, 그래프, 구현
정답자
아직 제출이 없습니다

문제

프로그래머 씨는 최근 자신의 멋진 스타트업 프로젝트를 만들느라 바빴다. 프로젝트는 Python으로 작성되었다. 지난 며칠 동안 그는 테스트 없이 소스 코드를 대규모로 리팩터링했다. 모든 수정을 마친 뒤 프로젝트를 실행해 보았지만, 소스 코드에 순환 의존성이 생겨 코드가 제대로 실행되지 않는다는 사실을 알게 되었다. 그는 코드를 조금 옮겨 보았지만 상황을 더 엉망으로 만들 뿐이었다. '모든 클래스를 한 파일로 옮기면 문제를 해결할 수 있을 텐데'라고 생각했지만, 그 계획도 통하지 않았다. 큰 좌절과 프로젝트를 최대한 빨리 출시해야 한다는 압박 속에서, 그는 마침내 올바른 순서로 정리하는 일을 알고리즘 전문가에게 맡기기로 했다.

소스 코드는 하나의 Python 파일이다. 여러 클래스로 이루어져 있다. 프로그래머 씨는 다중 상속을 별로 좋아하지 않아서, 코드의 각 클래스는 슈퍼 클래스를 최대 하나만 가진다. 클래스의 내용을 유출하고 싶지 않아서, 그는 내용을 비우고 Python의 “pass” 명령으로 대체했다. 따라서 어떤 클래스가 슈퍼클래스를 가지지 않으면 다음과 같다:

class <CLASS_NAME>:
    pass

어떤 클래스가 슈퍼클래스를 가지면 다음과 같다:

class <CLASS_NAME>(<SUPER_CLASS_NAME>):
    pass

위 코드에서 CLASS_NAME과 SUPER_CLASS_NAME은 임의의 Python 식별자이다. 더 자세한 내용은 예제 입력을 참고하라.

파일이 실행 가능하다는 것은, 슈퍼 클래스를 가지는 각 클래스에 대해 그 슈퍼클래스가 파일에서 그 클래스보다 앞에 나타나는 것을 뜻한다. 프로그래머 씨는 파일을 너무 많이 바꾸고 싶지 않아서, 최소한의 변경으로 파일을 올바른 순서로 만들고자 한다. 변경 한 번은 클래스 하나(그 내용 포함)를 잘라내어 파일의 다른 위치에 붙여넣는 것으로 센다. 파일이 실행 가능해지도록 하는 최소 변경 횟수를 구하라.

입력

입력은 python 파일이다. 빈 줄 하나로 구분된 여러 python 클래스로 이루어져 있다. 입력의 클래스들은 문제 설명에 나온 형식과 정확히 일치한다. 클래스 식별자는 영문 대소문자로만 이루어져 있으며 길이는 10자를 넘지 않는다(이 문제에서는 식별자에 대해 다른 가정을 해서는 안 된다). 각 “pass” 명령 앞에는 정확히 4개의 공백 문자가 있다. 파일에는 클래스가 최대 2,000개 있다. 모든 슈퍼 클래스는 파일 어딘가에 정의되어 있으며, 어떤 클래스도 여러 번 정의되지 않는다. 또한 클래스는 자기 자신의 슈퍼클래스가 아니다.

출력

파일이 실행 가능해지도록 해야 하는 최소 변경 횟수를 정수 하나로 출력하라. 불가능하면 -1을 출력하라.

예제1

  1. 예제 1

    입력
    class B(A):
    pass

class C(A):
    pass

class A:
    pass
    예상 출력
    1