[Java] 백준 BOJ / 1167번: 사이클 게임

사이클 게임

문제

---

문제 설명

점의 개수 n 과 진행된 차례의 수 m 이 주어지고 다음 m 줄 동안 두개의 점들을 고른다.

이렇게 계속 턴을 바꿔가며 점들을 고를 때 만약에 사이클이 완성 되었다면 해당 턴을 출력하고 마지막까지 사이클이 완성되지 않는다면 0 을 출력하는 문제이다.

---

구현

일단 사이클을 확인하는 문제이니 유니온파인드 알고리즘을 사용하였다.

일단 parent 라는 배열을 선언해두고 자기 자신을 값으로 가지도록 초기화 해준다.

parent = new int[n];
for (int i = 0; i < n; i++) {
	parent[i] = i;
}

그리고 나서 들어오는 두개의 점을 x, y 로 두고 각각 값에 대하여 find 함수를 실행시킨다.

find 함수는 사이클의 가장 윗단계를 찾는 과정이다.

함수의 인자로 들어오는 n 값에 대하여 parent[n] 값이 n 과 같다면 n을 그대로 리턴하고 그렇지 않다면 다시 재귀함수로 find(parent[n]) 을 리턴해준다.

public static int find(int n) {
	if (parent[n] == n) {
    	reutn n;
    } else {
    	reutn parent[n] = find(parent[n]);
    }
}

이렇게 나온 find(x) 값과 find(y) 값이 같다면 사이클이 완성되었다는 뜻이니 i + 1 을 리턴하고
그렇지 않다면 둘을 union 해주어야 한다.

union 함수 내에서는 입력으로 들어오는 두 값에 대하여 find 함수를 실행시키고 작은 값으로 합쳐주면 된다.

public static void union(int n1, int n2) {
	int p1 = find(n1);
    int p2 = fiind(n2);
    
    if(p1 < p2) {
    	parent[p2] = p1;
    } else {
    	parent[p1] = p2;
    }
}

---

코드

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

public class Main_20040 {

  static int[] parent;
  static int n, m;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    parent = new int[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }

    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken());
      int y = Integer.parseInt(st.nextToken());

      if (find(x) == find(y)) {
        System.out.println(i + 1);
        return;
      } else {
        union(x, y);
      }
    }
    System.out.println(0);
  }

  public static void union(int n1, int n2) {
    int p1 = find(n1);
    int p2 = find(n2);

    if (p1 < p2) {
      parent[p2] = p1;
    } else {
      parent[p1] = p2;
    }
  }

  public static int find(int n) {
    if (parent[n] == n) {
      return n;
    } else {
      return parent[n] = find(parent[n]);
    }
  }
}