[SWEA] 3289 서로소집합 (D4 / 서로소) - Java

링크

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

SW Expert Academy

 

 

 

문제 해석

- 문제 해석
서로소 테스트
결과로 1연산을 띄워쓰기 없이 출력

 

- 각 테스트 케이스 별 입력
첫 번째 줄 : N M # N : 자연수의 최대 값 / M : 연산의 개수
나머지 줄 : M번의 연산

 

연산이 0로 시작하면 합집합 
연산이 1로 시작하면 확인 연산

 

 

코드

import java.io.*;
import java.util.*;

public class Solution {
	
	static int[] parents;
	static int[] rank;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(st.nextToken());
		
		for(int test_case = 1; test_case <= T; test_case++) {			
			st = new StringTokenizer(br.readLine());	
			int N = Integer.parseInt(st.nextToken()); // 자연수 최대 값
			int M = Integer.parseInt(st.nextToken()); // 연산 횟수

			parents = new int[N + 1];
			rank = new int[N + 1];
			for (int i = 1; i <=N; i++) {
				parents[i] = i;
			}
			sb.append("#" + test_case + " ");
			
			for (int i = 0; i < M; i++) { 
				st = new StringTokenizer(br.readLine());
				
				int test = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if (test == 0) {
					union(a, b);					
					
				} else if (test == 1) {
					int pa = find(a);
					int pb = find(b);
					if (pa == pb) {
						sb.append(""+1);
					} else {
						sb.append(""+0);
					}
				}
				
			}
			sb.append("\n");
		} // [E] test_case
		System.out.println(sb);
	}

	private static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		
		parents[pa] = pb;
	}

	private static int find(int a) {
		if (parents[a] == a) {
			return a;
		} else {
			return parents[a] = find(parents[a]);
		}
	}
}

 

 

 

코드 해석

서로소를 익힐 수 있는 기본 문제입니다.

일반적인 코드를 이해한다면 쉽게 해결할 수 있습니다.

 

발생한 문제 & 해결 방안

parents 초기화 및 범위지정에서 틀려서 runtimeError가 떴다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice