0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [알고리즘] 창용 마을 무리의 개수 0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 이건 인접리스트를 만들고 dfs로 connected component의 수를 세는 문제라 ramen4598.tistory.com c++로 푼 적 있는 문제다. java로 다시 풀어보고, Union-Find로도 풀어보았다. 1. 문제 이해 인접리스트의 완전탐색 서로소 집합 (Union-Find) 2. 제출 가. DFS import java.io.Buff..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 서로소 집합 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class SWEA3289 { static int N, M; // 노드 수, 연산 수 static int[] p; // 부모 노드 저장 public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputSt..

1. 서로소 집합 Disjoint-set 상호 배타 집합 서로 중복되는 원소가 없는 집합들. 표현 연결 리스트 트리 연산 집합들을 식별하기 위해서 특정 멤버를 대표자로 사용한다. make-set(x) : 집합을 생성한다. 전처리 과정에서 단 한번 실행된다. find-set(x) : x가 속한 집합을 찾아서 대표자를 반환한다. Union(x, y) : x가 속한 집합과 y가 속한 집합을 합친다. Union-Find 연산이 핵심이다. 가. 연결 리스트로 구현 같은 집합의 원소들은 하나의 연결리스트로 관리 가장 앞의 원소를 대표자로 사용 각각의 원소는 자신의 대표자와 다음 원소를 가리키는 2개의 링크를 가진다. 연산의 편의성을 위해서 tail을 사용한다. Make-Set(a) : a를 대표자(rep)이자 ta..