영우는 사기꾼?

문제 설명

---

영우의 건설정보를 보고 거짓말을 했는지 안했는지 판별하는 프로그램을 만들어야 한다.

생각한 아이디어

---

영우가 거짓말을 한 경우

1. 해당 건물의 사전 조건을 만족하지 않는데 지어져 있다면 거짓말
2. 건물을 파괴할 때 안지어져 있을 때 파괴하자

풀이

---

>> 예외 상황

1. 중복된 건물이 건설될 경우, 이 경우 건물의 진입차수가 중복으로 내려가, 사전 조건을 만족하지 않음에도 불구하고 건물을 지울 수 있게 된다.

   • 이런 관계를 갖는 그래프일 때,

     • 1 → 2 → 3
     • 4→ 2

   • 영우의 입력에는

     1. 건설 1번
     2. 건설 1번
     3. 건설 2번

     이렇게 입력이 들어올 경우, 진입차수[2] = 2에서 진입차수가 0이되어 2번을 건설하게 된다.

     2번을 짓기 위해서는 1번과 4번이 건설이 되어야 하는데, 2번은 건설되지 않았는데 사전 조건을 만족한 것 처럼 된다.

2. 진입 차수 다시 늘리기

   건물이 딱 1개만 지울 수 있게 한 것이 아니다. 나는 n개를 지어도 1개만 카운팅했다.

   이런 관계를 갖는 그래프 일 때,

   1 → 2 → 3

   이런 경우

   1. 건설 1번

   2. 건설 1번

   3. 건설 1번

   4. 파과 1번

   5. 건설 2번

      마지막 4번째 명령에 의해 1번 건물은 파괴되었고 (0개인 상태) 5번 차례를 시작할 때, 진입차수가 다시 증가해 못짖게 했다.

      그러면 틀린다. 예제에서 이런 경우가 나온다

      제거된 대상에는 이제 진입 차수를 다시 늘려야 한다.

      3 2 5
      1 2
      2 3
      1 1
      1 2
      1 2
      2 2
      1 3

      즉,

      x - >z 의 그래프일 때, x 번 건물을 여러개 지을 수 있고 y(x>y )개 만큼 파괴한다면 건물을 최소 1개가 존재하므로

      ‘건설 z’의 명령문이 들어오면 건설할 수 있고 거짓말이 아니다.

      만약 x번 건물을 지은 뒤 x개만큼 파괴한다면 건물을 0개가 되고 진입차수를 늘려줘야 한다.