알고리즘 연습
[ 백준_BOJ ] 1717. 집합의 표현 _ JAVA 문제풀이
코딩하는 너구리
2019. 10. 16. 11:09
반응형
문제
풀이
Union-Find를 이용하여 풀이해야 하는 문제입니다.
0일 때 union 연산을 수행하고 1일 때 같은 집합에 있는지를 비교하기 때문에 flag 변수를 만들어서 분류해주었습니다.
문제에서 여러 번 isSame( ) 연산을 수행하기 때문에 StringBuilder( ) 를 이용해서 한 번만 출력할 수 있도록 해주었습니다.
추가적으로, union( ) 연산에서 연산의 수행속도를 높여주기 위해
x y 중 큰 수를 부모로 바꾸어주도록 하였습니다.
코드
출처
https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a
www.acmicpc.net
반응형