[SW expert Academy] SWEA 3289번 서로소 집합 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [SW expert Academy] SWEA 3289번 서로소 집합 자바(Java)

1) 난이도 : D4

 

2) 문제번호 : 3289번

 

3) 문제 출처

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr

SW Expert Academy

 

2. 문제

초기에 {1}, {2}, ... {n} 이 각각 n개의 집합을 이루고 있다.

여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

연산을 수행하는 프로그램을 작성하시오.

 

3. 제약사항

- 

 

4. 입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다.

m은 입력으로 주어지는 연산의 개수이다.

다음 m개의 줄에는 각각의 연산이 주어진다.

합집합은 0 a b의 형태로 입력이 주어진다.

이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다.

두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다.

이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

a와 b는 n 이하의 자연수이며 같을 수도 있다.

 

5. 출력

각 테스트 케이스마다 1로 시작하는 입력에 대해서 같은 집합에 속해있다면 1을, 아니면 0을 순서대로 한줄에 연속하여 출력한다.

 

6. 풀이

- 소스코드를 참고하면 된다.

- BufferedReader + StringBuilder를 사용했을 때, 실행시간 399ms이 나온다.

- BufferedReader + StringBuilder + System.out 사용했을 때, 실행시간 394ms가 나온다.

- StringBuilder에 연산자 사용 시 실행 시간이 늘어난다.

7. 소스 코드

import java.util.Scanner;

public class Solution {
	static int arr[]; // make 배열
	static int n; // n이하 자연수
	static int m; // 입력으로 주어지는 연산의 개수

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); // 테스트케이스 개수

		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt(); // n이하 자연수
			m = sc.nextInt(); // 입력으로 주어지는 연산의 개수
			// 각 집합의 부모를 담을 배열
			arr = new int[n + 1];

			make_set();
			
			System.out.printf("#%d ", tc);
			for (int i = 0; i < m; i++) {
				int oper = sc.nextInt();
				int a = sc.nextInt();
				int b = sc.nextInt();
				
				//합집합이 아니라면
				if (oper == 1) {
					int nA = find_set(a);
					int nB = find_set(b);
					if(equal(nA,nB)) System.out.print(1);
					else System.out.print(0);
					
				}
				//0이면 합집합
				else union_set(a,b);
			}
			System.out.println();
		}
	}

	// make_set
	public static void make_set() {
		for (int i = 1; i <= n; i++)
			arr[i] = i;
	}

	// find_set
	public static int find_set(int a) {
		if (arr[a] == a)
			return a;

		return arr[a] = find_set(arr[a]);
	}

	// union_set
	public static boolean union_set(int a, int b) {
		int aRoot = find_set(a);
		int bRoot = find_set(b);

		if (aRoot == bRoot)
			return false;

		arr[bRoot] = aRoot;
		return true;
	}
	
	//같은지
	public static boolean equal(int a, int b) {
		if(a==b) return true;
		else return false;
	}
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Solution {
	static int arr[]; // make 배열
	static int n; // n이하 자연수
	static int m; // 입력으로 주어지는 연산의 개수

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			StringBuilder sb = new StringBuilder();
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			// 각 집합의 부모를 담을 배열
			arr = new int[n + 1];

			make_set();
			
//			sb.append("#" + tc + " ");
			
			sb.append("#");
			sb.append(tc);
			sb.append(" ");
			
//			System.out.printf("#%d ", tc);
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int oper = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				//합집합이 아니라면
				if (oper == 1) {
					int nA = find_set(a);
					int nB = find_set(b);
					if(equal(nA,nB)) sb.append(1);
					else sb.append(0);
					
				}
				//0이면 합집합
				else union_set(a,b);
			}
			System.out.println(sb);
		}
	}

	// make_set
	public static void make_set() {
		for (int i = 1; i <= n; i++)
			arr[i] = i;
	}

	// find_set
	public static int find_set(int a) {
		if (arr[a] == a)
			return a;

		return arr[a] = find_set(arr[a]);
	}

	// union_set
	public static boolean union_set(int a, int b) {
		int aRoot = find_set(a);
		int bRoot = find_set(b);

		if (aRoot == bRoot)
			return false;

		arr[bRoot] = aRoot;
		return true;
	}
	
	//같은지
	public static boolean equal(int a, int b) {
		if(a==b) return true;
		else return false;
	}
}

---