[BOJ] 백준 1717 집합의 표현 (Swift)

문제

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

1717번: 집합의 표현

풀이

유니온 파인드로 풀이할 수 있는 문제입니다.
https://dev-mandos.tistory.com/296

[알고리즘] 유니온 파인드(Union-Find) (Swift)

먼저 노드별로 부모노드를 값으로 가질 Int 배열을 선언해주고, 초기 값은 자기 자신의 번호를 가르키도록 하였습니다.

부모 노드를 찾을 수 있는 find 연산을 구현하였습니다.
합집합 연산을 구현하는 방식은 1과 2에 대해서 합집합 연산을 하게되면 1과 2의 부모를 찾고,
찾은 부모를 다른 노드의 자식으로 연결시키는 방식으로 구현할 수 있습니다.

소스코드

	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 merge(_ 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 = ""
	for _ in 0..<m {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let isUnion = input[0] == 0, a = input[1], b = input[2]
	if isUnion {
	merge(a, b)
	} else {
	answer += isSameParent(a, b) ? "YES\n" : "NO\n"
	}
	}
	print(answer)

view raw 집합의 표현.swift hosted with ❤ by GitHub

후기

유니온 파인드에 대해 이해하고 있다면 쉽게 풀 수 있는 문제였습니다.