[SWEA] 7465 창용마을무리의개수 (D4 / 서로소) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE&problemTitle=7465&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제 해석

- 각 테스트 케이스 별 입력
첫 번째 줄 : N M # 사람 수, 관계 수
나머지 줄  : 사람1 사람2의 관계 표현

서로 관계로 엮여 있으면 하나의 무리라고 가정함
몇 개의 무리가 존재하는지 계산

 

코드

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

public class Solution {

	static int[] parents;
	static int answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		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()); // 관계 수

			answer = 0;
			parents = new int[N + 1];
			for (int i = 1; i < parents.length; i++) {
				parents[i] = i;
			}

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				union(a, b);

			}

			// 본인이 대표 노드인 경우
			for (int i = 1; i < parents.length; i++) {
				if (parents[i] == i) {
					answer++;
				}
			}
			System.out.println("#" + test_case + " " + answer);

		}
	} // [E] test_case

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

		if (pa != pb) {
			parents[pa] = pb;
		}

	}

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

	}
}

 

 

 

코드 해석

서로소 기본 개념으로 풀 수 있는 문제입니다.

 

서로소의 묶음을 찾는 방법으로 parents에서 본인이 대표자인 노드인 경우에만 값을 추가하도록 구현하였습니다. 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

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

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

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