[BOJ] 백준 20040 사이클 게임 (Swift)

문제

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

풀이

유니온 파인드 알고리즘을 활용하여 풀이할 수 있는 문제입니다.

사이클이 완성되는 경우는 어떠한 경우일까요?
현재 1, 2, 3이 다음과 같이 연결되어있다고 가정해봅시다.

현재 2와 3의 부모노드는 1로 같습니다. 2와 3을 연결하면 사이클을 발생시킵니다.
즉, 같은 부모노드를 가진 것 끼리 연결하게 된다면 사이클이 생성되게 됩니다.

그러므로, 연결을 하기 전에 같은 두 노드가 같은 부모노드인지 확인을 하고 같은 부모노드라면 연결을 하게되면 사이클이 발생되므로
그 당시의 차례의 번호를 출력해주면 됩니다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], m = input[1]
	var parent = [Int](0..<n)
	func find(_ x: Int) -> Int {
	if parent[x] == x {
	return x
	}
	parent[x] = find(parent[x])
	return parent[x]
	}
	func union(_ a: Int, _ b: Int) {
	let a = find(a)
	let b = find(b)
	if a == b {
	return
	}
	if a > b {
	parent[a] = b
	} else {
	parent[b] = a
	}
	}
	func isSameParent(_ a: Int, _ b: Int) -> Bool {
	return find(a) == find(b)
	}
	var answer = 0
	for i in 1...m {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a = input[0], b = input[1]
	if isSameParent(a, b) {
	answer = i
	break
	}
	union(a, b)
	}
	print(answer)

view raw 사이클 게임.swift hosted with ❤ by GitHub

후기

유니온 파인드를 활용한 문제이며, MST를 알고있었다면 쉽게 풀 수 있는 문제였습니다.