[ SWEA / 자바 ] 7465번 창용 마을 무리의 개수

 

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

SW Expert Academy

📑 문제

 

N명의 사람이 M개의 관계를 형성하고 있을 때 총 몇 개의 무리가 지어지는지 출력하는 문제

 

💡 입력

✔ 맨 첫 줄은 테스트케이스 수

✔ 각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수 N과 서로를 알고 있는 사람의 관계 수 M 제시

✔ N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2)

✔ M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호 제시

✔ 같은 관계는 반복해서 주어지지 않음

 

 

 

---

 

---

✨ 풀이과정

✔ 창용마을 사람을 정점으로, 관계 수를 간선으로 간주한다

✔ 관계 배열을 만들어 시작정점과 도착정점을 저장한다

 

✔ 서로 관계를 맺고 있을 때, 대표자(루트)의 수가 무리의 개수이므로 대표자를 나타낼 배열 p를 생성한다

     ✔ 처음 대표자를 초기화 할 때는 자기 자신이 대표이다. (make-set)

✔ 각 정점의 대표를 확인한 후(findSet) 연결된 정점인데 대표가 다르다면 대표를 바꿔준다(union)

 

✔ 겹치지 않는 대표자(루트)를 리스트에 추가한다

⇒ 리스트의 크기가 무리의 개수가 된다.

 

 

---

---

📑 코드

package DAY0929;

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {

	static int[] p; // 대표자 배열

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {

			int N = sc.nextInt(); // 창용마을 사람 수 //정점
			int M = sc.nextInt(); // 서로를 알고 있는 사람의 관계 수 //간선

			// 간선의 배열을 저장해봅시다
			int[][] edges = new int[M][2];

			for (int i = 0; i < M; i++) {
				edges[i][0] = sc.nextInt(); // 시작정점
				edges[i][1] = sc.nextInt(); // 도착정점
			}

			p = new int[N + 1];

			for (int i = 1; i < N + 1; i++) {
				makeSet(i);
			}

			for (int i = 0; i < M; i++) {

				// i번째 두 정점의 대표를 확인한다
				int px = findSet(edges[i][0]); // 시작정점
				int py = findSet(edges[i][1]); // 끝정점

				// 연결된 정점인데 대표가 다르다면
				if (px != py) {
					union(px, py); // 대표 바꿔!!
				}
			}

			// 몇개의 무리가 있는지
			ArrayList<Integer> list = new ArrayList<>();
			
			while(N>0) {
				
				int FS = findSet(N); //사람 N의 대표자를 찾으세요
				if(list.size()==0) list.add(FS); 
				else {
					int check = 0; //중복체크
					for(int i=0; i<list.size(); i++) {
						if(FS == list.get(i)) check++;
					}
					
					if(check==0) list.add(FS);
				}
				
				N--;
			}
			
			int ans = list.size(); //대표자의 수 == 무리의 수
			System.out.println("#"+tc+" "+ans);
			
		}//testCase
	} //main

	private static void union(int px, int py) {
		p[findSet(py)] = findSet(px); // py의 대표를 px의 대표로 바꾸삼
	}

	private static int findSet(int x) {

		if (x == p[x])
			return x;
		return findSet(p[x]);

	}

	private static void makeSet(int x) {
		// 자기자신으로 대표 초기화
		p[x] = x;
	}
}

---

---