[BOJ] 20040 사이클 게임 - JAVA

1. 문제

20040번: 사이클 게임

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

---

2. 풀이

• 유니온 파인드는 여러번 풀이해서 자세하게는 하지 않겠다.
• 이 문제는 따로 union 함수를 만들지 않고 입력받는 메인함수 내에서 처리했다. 루트가 같다면 바로 그 행을 출력하고 메인을 끝내려고 했기 때문이다.
• 모두 입력을 받고나서도 함수가 끝나지 않았다면 사이클이 없는 것이므로 0을 출력한다.

import java.io.*;
import java.util.*;

public class BOJ_20040_사이클게임 {
   static int[] set;
   static int N,M;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      set = new int[N];
      for(int i=1;i<N;i++) set[i] = i;

      for(int i=1;i<=M;i++){
         st = new StringTokenizer(in.readLine());
         int a = find(Integer.parseInt(st.nextToken()));
         int b = find(Integer.parseInt(st.nextToken()));

         if(a==b){
            System.out.println(i);
            return;
         }

         if(a>=b) set[b] = a;
         else set[a] = b;

      }
      System.out.println(0);
   }

   private static int find(int x) {
      if(set[x]==x) return x;
      return set[x] = find(set[x]);
   }
}

---

3. 결과

똑같이 유니온파인드를 이용한 [1717 집합의 표현] 문제에서도 그랬지만 static으로 n,m을 빼냐 마냐에 따라서 시간과 메모리 차이가 많이 난다. 위의 결과가 static으로 뺀 결과다. 

왜 그럴지 생각해봤는데, 백준의 채점서버가 static은 내버려두고 내 main함수만 다시 돌리면서 채점하는게 아닐까 싶다. 그렇게되면 n,m을 할당하는 시간이 줄어들어서 시간, 메모리 두가지 측면에서 모두 차이가 나는 게 설명된다.

하지만 이건 가설일 뿐이고 실제 이유가 뭔지 정말 궁금하다.