너구리의 코딩 블로그
반응형
문제
풀이
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
반응형
'알고리즘 연습' 카테고리의 다른 글
| [ 백준_BOJ ] 2564. 경비원 _ JAVA 문제풀이 (0) | 2019.10.16 |
|---|---|
| [ SWEA ] 1868. 파핑파핑 지뢰찾기 _ JAVA 문제풀이 (1) | 2019.10.16 |
| [백준_BOJ] 1157. 단어공부 _ JAVA 문제풀이 (0) | 2019.10.16 |
| [ 수학 ] 최대공약수와 최소공배수 연습하기 JAVA (0) | 2019.10.16 |
| [SWEA] 2046. 스탬프 찍기 문제풀이 JAVA (0) | 2019.10.09 |