[아이디어] 게임

문제

n개의 노드로 이루어진 그래프가 있다. 이 그래프를 가지고 A, B가 게임을 하는데, A는 질문을 하고 B는 이 질문에 대해 답을 한다. 만약 질문을 하는 쪽이 그래프가 연결 그래프라는 것을 알게 되면 게임은 끝난다. 게임을 재미있게 하기 위해서, B는 모든 가능한 질문인 (n,2)개의 질문을 다 한 다음에야 A가 연결 그래프라는 사실을 알게 하고 싶다. B는 그래프를 미리 그리지 않고, A의 질문에 대해 답을 하면서 그래프를 그려나간다. A를 가장 괴롭게 할 수 있는 B의 답을 구하시오.

문제 설명

A는 그래프가 연결 그래프인 것을 알고 있다고 가정합니다. 그리고 A는 B에게 어떤 두 노드를 이야기하고, B는 이 두 노드를 연결할지 말지 결정합니다. B는 A의 질문에 에지를 연결할 수도 아닐 수도 있지만, 최종적으로는 (n,2)개의 질문 안에 모든 노드들을 연결해야합니다.

풀이

A가 B에게 물어보는 노드의 번호는 먼저 부르는 것이 작다고 가정하고 설명합니다. B가 A를 괴롭히기 위헤서는 마지막 노드를 최대한 그래프와 늦게 연결시키는 것이 중요합니다. 그래서 일단 $N_{2}-1$개의 질문에 어떻게 답할지는 모르겠지만 마지막 질문에는 YES라고 해야한다는 것을 알았습니다.

바꿔 생각해서 연결 그래프의 정의를 생각해보겠습니다. 어떤 한 노드는 다른 노드 중 하나와는 연결되어있어야 합니다. 그리고 이 특성은 모든 노드에 적용됩니다. 따라서 A가 물어보는 질문을 구성하는 노드들을 잘 듣습니다. 그리고 그 노드가 몇 번 나왔는지 count를 합니다. 질문에 포함된 두 노드 중 하나라도 $N-1$번째 나온 질문은 반드시 YES라고 해야합니다. 이 질문마저 노드를 연결해주면 연결그래프에 포함되지 않는 노드가 나오기 때문입니다.

예시

1 2
3 4

노드가 위와 같이 있을 때, 할 수 있는 모든 질문은 아래와 같습니다.

1 2
1 3
1 4 <- 1이 3번째 (N-1번째)나오므로 edge 그리기
2 3
2 4 <- 2이 3번째 (N-1번째)나오므로 edge 그리기
3 4 <- 3이 3번째 (N-1번째)나오므로 edge 그리기