https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용해 최소 신장 트리를 구하되, 간선을 선택할 때 여초와 여초, 남초와 남초가 이어진 경우는 제외한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import..

https://www.acmicpc.net/problem/1325

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드 알고리즘을 쓰는 문제이다. 초기에는 0부터 n까지 각각의 숫자만 담은 집합이기 때문에, 부모 배열에 자기 자신을 넣는다. 부모를 찾는 find 함수와 두 원소의 부모를 합치는 union 함수를 만든다. find 함수의 경우, 부모노드가 자기자신인 루트노드를 찾을 때까지 재귀하는 형태이다. union함수의 경우 원소 두 개의 부모를 각각 찾아..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 두가지 방법으로 해결하였다. Union Find 사용 Union 함수와 Find 함수를 만들어서 이어지는 지역끼리 부모가 같도록 만들어주었다. 여행 계획에서 부모가 다른 지역이 나타나면 NO를 출력한다. ArrayList 사용 ArrayList에 연결된 지역을 각각 담아주었다. 여행 계획에 나타나는 지역마다 BFS를 이용해 연결되는지 확인하고 그렇지 않다면 NO를 출력한다. 메모리와 시간 모..