📙 Algorithm Solving/Java
📙[Algo] 24.04.11 알고리즘
혜덕hyeduck
2024. 4. 14. 17:37
알고리즘 문제) BOJ 1717. 집합의 표현
문제 요약
- 초기 N+1개 집합이 존재 {0}, … , {N}
- 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되는지 확인하는 연산 수행하려고 함
- 이를 표현하는 프로그램 작성
시간 제한
- 2초
입력
- N M(연산 개수)
- 1 ≤ N ≤ 100만
- 1 ≤ M ≤ 10만
- M개의 줄에 각각 연산이 주어짐
- 합집합 : 0 a b → a가 포함되어 있는 집합, b가 포함되어 있는 집합 합치기
- 같은 집합인지 확인 : 1 a b
- 0 ≤ a,b≤n ⇒ a,b는 정수이며 같을 수도 있다.
출력
- 1로 시작하는 입력에 a와 b가 같으면 YES(또는 yes) 그렇지 않다면 NO(또는 no)출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] parent;
// 집합 합치기
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
parent[b] = a;
}
// 루트 노드 찾기
static int find(int x) {
// 부모노드와 나와 같으면 대장(루트 노드)
if (parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[1000010];
for (int i = 0; i < 1000010; i++) {
parent[i] = i;
}
int cmd, a, b;
StringBuilder sb = new StringBuilder();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
cmd = Integer.parseInt(st.nextToken());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
switch (cmd) {
case 0:
// 집합 합치기
union(a, b);
break;
case 1:
// 같은 집합인지 확인
if (find(a) == find(b)) {
sb.append("YES\\n");
} else {
sb.append("NO\\n");
}
break;
}
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 18116. 로봇 조립
문제 요약
- 부품은 1부터 1000000까지 정수로 표현 됨
- 부품 i가 속한 로봇은 robot(i)라고 표현
- 예를 들어, 부품 11과 부품 22가 로봇 A의 부품이라면 robot(11)은 로봇 A, robot(22)도 로봇A
- 서로 다른 로봇은 공통 부품을 갖지 않음
- 다음 2가지 지시를 하려고 함
- 서로 다른 부품 2개가 같은 로봇의 부품이라는 것을 알려줌
- 부품 i에 대해서, 지금까지 알아낸 robot(i)의 부품이 몇 개냐고 물어봄
시간 제한
- 4초
입력
- 호재 지시 횟수 N
- 1≤N≤100만
- N개의 지시가 주엉짐
- 두 부품이 같은 로봇 껀지?
- I a b
- 1≤a,b≤100만, a≠b, a,b는 정수
- I a b
- 어떤 로봇의 부품이 몇 개인지?
- Q c
- 1≤c≤100만, c는 정수
- Q c
- 두 부품이 같은 로봇 껀지?
출력
- Q로 시작하는 명령에 대해, 해당 로봇의 부품 개수를 출
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] parent;
static int[] size;
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (size[a] < size[b]) {
parent[a] = b;
size[b] += size[a];
} else {
parent[b] = a;
size[a] += size[b];
}
}
static int find(int x) {
if (parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
N = Integer.parseInt(br.readLine());
parent = new int[1000010];
for (int i = 0; i < 1000010; i++) {
parent[i] = i;
}
size = new int[1000010];
Arrays.fill(size, 1);
char cmd;
int a, b, robot, root;
while (N-- > 0) {
st = new StringTokenizer(br.readLine());
cmd = st.nextToken().charAt(0);
switch (cmd) {
case 'I' :
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
union(a, b);
break;
case 'Q':
robot = Integer.parseInt(st.nextToken());
root = find(robot);
sb.append(size[root] + "\\n");
break;
}
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 11724. 연결 요소의 개수
문제 요약
- 무방향 그래프가 주어졌을 때, 연결 요소 개수 구하기
시간 제한
- 3초
입력
- 정점 개수 N, 간선 개수 M
- 1 ≤ N ≤ 1000
- 0 ≤ M ≤ N*(N-1)/2
- 둘째 줄부터 M개의 줄에 간선의 양 끝점 u v가 주어짐
- 1≤u,v≤N, u≠v
출력
- 연결 요소 개수 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] parent;
static int find(int x) {
if (parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
parent[b] = a;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[N + 10];
for (int i = 0; i < N + 10; i++) {
parent[i] = i;
}
int a, b;
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
union(a, b);
}
Set<Integer> set = new TreeSet<>();
for (int i = 1; i <= N; i++) {
set.add(find(i));
}
bw.write(String.valueOf(set.size()));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 16562. 친구비
문제 요약
- 학생 i에게 Ai만큼 돈을 주면 친구가 될 수 있다
- 친구가 되면 그 친구의 친구도 친구다
- 총 k원이 있을 때, 최소 비용으로 모든 사람과 친구가 되는 법은?
시간 제한
- 2초
입력
- 학생 수 N, 친구 관계 수 M, 가지고 있는 돈 K
- 1≤N≤1만
- 0≤M≤1만
- 1≤K≤1000만
- N개의 각각 학생이 원하는 친구비 Ai가 주어진다
- 1≤Ai≤1만
- 1≤i≤N
- 다음 M개의 줄에 숫자 v w가 주어짐
- 학생 v와 학생 w가 서로 친구
- 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수 있음
출력
- 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소 비용은?
- 만약 친구를 다 사귈 수 없다면 on no 출력
접근법
1 2 3 4 5
(1 3)
(4 2 5)
연결 요소마다 비용이 가장 작은 친구와 사귄다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, K; // 학생 수 N, 친구 관계 수 M, 가지고 있는 돈 K
static int[] money; // 친구비
static int[] parent;
static int find(int x) {
if (parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
parent[b] = a;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
money = new int[N + 1];
parent = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
parent[i] = i;
}
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
money[i] = Integer.parseInt(st.nextToken());
}
int a, b;
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
union(a, b);
}
int p, answer = 0;
int[] cost = new int[N + 1];
Arrays.fill(cost, 1 << 30);
for (int i = 1; i <= N; i++) {
p = find(i);
cost[p] = Math.min(cost[p], money[i]);
}
for (int i = 1; i <= N ; i++) {
if (cost[i] != 1 << 30) {
answer += cost[i];
}
}
if (answer > K) {
bw.write("Oh no");
} else {
bw.write(String.valueOf(answer));
}
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1197. 최소 스패닝 트리
문제 요약
- 그래프가 주어졌을 때, 최소 스패닝 트리 구하는 문제
시간 제한
- 1초
입력
- 정점 개수 V, 간선 개수 E
- 1≤V≤1만
- 1≤E≤10만
- E개의 줄에 간선 정보 A, B, C가 주어짐
- A와 B가 가중치 C간선으로 연결되어 있음
- C는 -100만 ~ 100만
출력
- 첫째 줄에 최소 스패닝 트리의 가중치를 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int V, E;
static int[][] graph;
static int[] parent;
static int find(int x) {
if (parent[x] == x) {
return x;
} else {
parent[x] = find(parent[x]);
return parent[x];
}
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
parent[b] = a;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
graph = new int[E][3]; // {비용, 노드1, 노드2}
int a, b, c;
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
graph[i][0] = a;
graph[i][1] = b;
graph[i][2] = c;
}
Arrays.sort(graph, (o1, o2) -> {
return o1[2] - o2[2];
});
parent = new int[V + 1];
for (int i = 0; i < V + 1; i++) {
parent[i] = i;
}
int answer = 0;
for (int i = 0; i < E; i++) {
a = graph[i][0];
b = graph[i][1];
c = graph[i][2];
if (find(a) == find(b)) continue;
union(a, b);
answer += c;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 21815. Portals
문제 요약
- 도시가 2N개가 있고, 도로도 2N개가 존재한다.
- N줄에 걸쳐서 각각 도시를 연결한 도로 정보가 2쌍씩 주어지며, 그 두 쌍의 순서를 바꾸기 위한 비용도 앞에 함께 주어진다.
- ex) 10 1 4 8 9 가 주어지면 도시1 - 도시4, 도시8-도시9가 각각 연결되어있다. 이때 만약 도시 순서를 바꿔서 연결할 경우(도시1-도시8, 도시4-도시9) 비용이 10든다.
- 어떤 도시든 무조건 도로 2개가 연결되어 있다.
- 모든 도시가 하나의 연결 요소가 되도록 만들기 위한 최소 비용을 구하는 문제
시간 제한
- 1초
입력
- N이 입력으로 주어짐
- N개의 줄에 교체 비용과 도시 연결 정보(2쌍) (a, b) (c, d)가 주어짐
출력
- 모든 도시가 하나의 연결요소가 되기 위한 최소 비용 구하기
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] graph;
static int[] parent;
static int find(int x) {
if (parent[x] == x) return x;
parent[x] = find(parent[x]);
return parent[x];
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
parent[b] = a;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
graph = new int[N][3];
parent = new int[2 * N + 10];
for (int i = 0; i < 2 * N + 10; i++) {
parent[i] = i;
}
int cost, v1, v2, v3, v4;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
cost = Integer.parseInt(st.nextToken());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
v3 = Integer.parseInt(st.nextToken());
v4 = Integer.parseInt(st.nextToken());
union(v1, v2);
union(v3, v4);
graph[i][0] = cost;
graph[i][1] = v1;
graph[i][2] = v3;
}
Arrays.sort(graph, (o1, o2) -> {
return o1[0] - o2[0];
});
int c, a, b;
int answer = 0;
for (int i = 0; i < N; i++) {
c = graph[i][0];
a = graph[i][1];
b = graph[i][2];
if (find(a) == find(b)) continue;
union(a, b);
answer += c;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}