📙 Algorithm Solving/Java
📙[Algo] 24.07.11~24.07.12 알고리즘
혜덕hyeduck
2024. 7. 12. 15:48
알고리즘 문제) BOJ 1043. 거짓말
문제 요약
- 지연이는 거짓말하는 걸 좋아한다.
- 파티에가서 거짓말을 하기 위해서는, 진실을 아는 사람이 있으면 안되고, 진실을 아는 사람과 같은 파티였던 사람이 있는 곳도 안된다.
- 이때, 거짓말을 할 수 있는 파티 개수는?
시간 제한
- 2초
입력
- 사람 수 N, 파티 수 M
- N과 M은 50이하 자연수
- 진실을 아는 사람 수와 사람의 번호가 주어짐
- 사람의 번호는 1~N
- 진실을 아는 사람 수는 0이상 50이하 정수
- M개의 줄에는 각 파티마다 오는 사람 수와 사람 번호가 차례로 주어진다.
- 각 파티에 오는 사람 수는 1이상 50이하 정수
출력
- 거짓말을 할 수 있는 파티 개수
접근법
- UNION & FIND로 풀었다,
- 같은 파티에 참석한 경우 Union으로 묶어주는데, 이때 진실을 아는 사람이 존재한다면, 해당 사람을 부모로 하게끔했다.
- 이후 파티 참석인 대표를 담은 party배열을 돌며 find값(부모)이 진실을 아는 사람이 아닐 경우에만 카운트
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static boolean[] know;
static int[] parent;
static int[] party;
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;
if (know[b]) parent[a] = b;
else parent[b] = a;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
know = new boolean[N + 1];
parent = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
parent[i] = i;
}
party = new int[M];
st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
for (int i = 0; i < k; i++) {
know[Integer.parseInt(st.nextToken())] = true;
}
int prv, cur;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
k = Integer.parseInt(st.nextToken());
prv = Integer.parseInt(st.nextToken());
party[i] = prv;
for (int j = 0; j < k - 1; j++) {
cur = Integer.parseInt(st.nextToken());
union(prv, cur);
prv = cur;
}
}
int cnt = 0;
for (int i = 0; i < M; i++) {
if (!know[find(party[i])]) cnt++;
}
System.out.println(cnt);
}
}
알고리즘 문제) BOJ 1477. 휴게소 세우기
문제 요약
- 휴게소 N개 존재
- 이때, 휴게소 위치는 고속도로 시작에서 어느정도 떨어져 있는지로 주어짐
- 고속도로 끝 또는 이미 휴게소있는 곳을 제외하고 휴게소 M개를 더 세우려고 한다.
- 이때, 휴게소가 없는 구간의 길이 최댓값을 최소로하려고 할때, 그 최솟값을 구해라
시간 제한
- 2초
입력
- 휴게소 개수 N, 더 지으려고 하는 휴게소 개수 M, 고속도로 길이 L
- 0 ≤ N ≤ 50
- 1 ≤ M ≤ 100
- 100 ≤ L ≤ 1,000
- 1 ≤ 휴게소의 위치 ≤ L-1
- N+M < L
- 현재 휴게소 위치가 공백을 두고 주어짐
- N이 0일경우 빈줄
- 위치는 중복X, 정수로 주어짐
출력
- M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값
접근법
- 이분탐색을 진행하며, mid값에 휴게소가 없는 구간의 최댓값을, install에는 설치해야할 휴게소 개수를 저장했다.
- 고속도로 끝 구간부터 탐색을 진행하며,
- 휴게소가 없는 구간이 mid보다 크거나 같을 경우, 휴게소를 설치했다.
- 이때, 이때, mid보다 작은 구간을 만들어여 하므로, dist / mid 만큼 install에서 차감했다.
- 만약 install 값이 음수일 경우, 최대구간을 너무 좁게 잡은 것이므로 구간 너비를 늘리고자 s = mid +1 했고,
- 그게 아닐 경우, 최댓값의 최솟값을 찾기 위해 answer변수에 mid값 저장 후, e = mid -1 했다.
- 휴게소가 없는 구간이 mid보다 크거나 같을 경우, 휴게소를 설치했다.
- 주의할 점은
- s를 0부터 할 경우 /by zero 오류가 뜨므로, s=1부터…
- 또한 끝 구간에는 휴게소를 설치할 수 없으므로 e=L-1부터..
- 또한, 설치하지 않는 구간의 길이(dist)를 구할 때, 1을 추가로 빼주었다.
- 이미, 휴게소가 설치 된 곳에는 설치할 수 없기 때문이다.
- 또한 휴게소 시작 구간은 1이아닌 0이다!
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, L;
static int[] arr;
static int parametricSearch() {
int s = 1, e = L - 1, mid, dist, install, ans = -1;
while (s <= e) {
mid = (s + e) / 2; // 휴게소 없는 구간의 최댓값
install = M;
for (int i = 0; i < N + 1; i++) {
// 휴게소를 설치하지 않은 구간 길이
dist = arr[i + 1] - arr[i] - 1;
// 만약 구간 길이가 mid보다 크거나 같다면
// 휴게소를 설치해준다. 이때, mid보다 작은 구간을 만들어여 하므로
// dist / mid 만큼 install에서 차감했다.
if (dist >= mid) {
install -= dist / mid;
}
}
if (install < 0) {
// 구간을 작게 잡아, 너무 많은 휴게소를 설치한 것이므로
// 구간을 늘린다.
s = mid + 1;
} else {
// 최댓값의 최솟값을 찾아야 하므로
// 정답변수에 저장하고, 구간 줄이기
ans = mid;
e = mid - 1;
}
}
return ans;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 설치된 휴게소 개수
M = Integer.parseInt(st.nextToken()); // 세워야할 휴게소 개수
L = Integer.parseInt(st.nextToken()); // 고속도로 길이
arr = new int[N + 2];
arr[0] = 0;
arr[N + 1] = L;
if (N != 0){
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
}
Arrays.sort(arr);
System.out.println(parametricSearch());
}
}
알고리즘 문제) BOJ 2660. 회장뽑기
문제 요약
- 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.
- 만약, 회원이 다른 모든 회원과 친구라면 1점
- 다른 모든 회원이 친구 또는 친구의 친구라면 2점
- 친구의 친구의 친구까지 있다면 3점
- 이런식으로 부여된다.
- 단, 만약 어떤 두회원이 친구사이이면서, 친구의 친구사이이면 친구사이라고 본다.
- 이때, 회원들 중 가장 점수가 작은 사람을 회장으로 선출할 때, 회장이 될 수 있는 모든 사람알 찾아라
시간 제한
- 1초
입력
- 회원의 수
- 50이하
- 둘째 줄부터 친구 사이인 두 회원의 번호가 주어진다
- 회원 번호는 1부터 회원 수만큼 주어진다
- 마지막 줄에는 -1 -1이 주어진다.
출력
- 첫째 줄에 회장 후보의 점수와 후보의 수
- 둘째 줄에는 회장 후보를 오름차순으로 출력
접근법
- BFS 알고리즘
- 한 노드부터 다른 노드까지의 최단 경로 중 가장 긴 경로를 찾도록 했다.
- bfs알고리즘을 돌며 경로 크기를 저장할 dist변수 사용
- 한 노드부터 다른 노드까지의 최단 경로 중 가장 긴 경로를 찾도록 했다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Integer>[] lst;
static Queue<Integer> q = new LinkedList<>();
static boolean[] visited;
static int bfs(int start) {
q.offer(start);
visited[start] = true;
int cur, size, dist = 0;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
cur = q.poll();
for (Integer nxt : lst[cur]) {
if (visited[nxt]) continue;
visited[nxt] = true;
q.offer(nxt);
}
}
dist++;
}
return dist - 1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
lst = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
lst[i] = new ArrayList<>();
}
visited = new boolean[N + 1];
int a, b;
while (true) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
if (a == -1) break;
lst[a].add(b);
lst[b].add(a);
}
int min = 1 << 30, ret;
Queue<Integer> ans = new LinkedList<>();
for (int i = 1; i <= N; i++) {
ret = bfs(i);
if (min > ret) {
if (!ans.isEmpty()) ans.clear();
ans.offer(i);
min = ret;
} else if (min == ret) {
ans.offer(i);
}
Arrays.fill(visited, false);
}
StringBuilder sb = new StringBuilder();
sb.append(min).append(" ").append(ans.size()).append("\n");
while (!ans.isEmpty()) {
sb.append(ans.poll()).append(" ");
}
System.out.println(sb);
}
}
알고리즘 문제) BOJ 17141. 연구소 2
문제 요약
- N*N 크기 연구소가 있으며, 연구소에는 바이러스를 놓을 수 있는 곳이 있다.
- 바이러스 M개를 놓을 수 있는 임의의 위치에 두고, 퍼뜨릴때, 모든 빈 칸에 바이러스를 퍼뜨릴 수 있는 최소 시간을 구해라
시간 제한
- 1초
입력
- 연구소 크기 N, 놓을 수 있는 바이러스 개수m M
- 5 ≤ N ≤ 50
- 1 ≤ M ≤ 10
- N개의 줄에 연구소 상태가 주어짐
- 0 : 빈칸, 1 : 벽, 2 : 바이러스 놓을 수 있는 칸
- 2의 개수는 M보다 크고 10보다 작거나 같은 자연수
출력
- 모든 빈칸에 바이러스가 있게 되는 최소 시간은?
- 만약 모든 빈 칸에 퍼뜨릴 수 없다면 -1 출력
접근법
BFS + 조합
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static ArrayList<int[]> virusIdx = new ArrayList<>();
static Queue<int[]> q = new LinkedList<>();
static boolean[][] visited;
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int empty;
static int min = 1 << 30;
static int spreadVirus() {
int cr, cc, mr, mc, size, time = 0, remain = empty - M;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
cr = q.peek()[0];
cc = q.poll()[1];
for (int dir = 0; dir < 4; dir++) {
mr = cr + delR[dir];
mc = cc + delC[dir];
if (mr < 0 || mc < 0 || N <= mr || N <= mc) continue;
if (visited[mr][mc] || map[mr][mc] == 1) continue;
visited[mr][mc] = true;
q.offer(new int[]{mr, mc});
remain--;
}
}
time++;
}
if (!q.isEmpty()) q.clear();
for (boolean[] v : visited) {
Arrays.fill(v, false);
}
if (remain <= 0) return time - 1;
else return 1 << 30;
}
static void recur(int cur, int start) {
if (cur == M) {
for (int i = 0, len = virusIdx.size(); i < len; i++) {
if (virusIdx.get(i)[2] == 1) {
// 바이러스를 놓은 곳만 큐에 담기
visited[virusIdx.get(i)[0]][virusIdx.get(i)[1]] = true;
q.add(new int[]{virusIdx.get(i)[0], virusIdx.get(i)[1]});
}
}
int ans = spreadVirus();
min = Math.min(ans, min);
return;
}
// 바이러스 M개 놓는 경우 선택하기
for (int i = start, len = virusIdx.size(); i < len; i++) {
virusIdx.get(i)[2] = 1;
recur(cur + 1, i + 1);
virusIdx.get(i)[2] = 0;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) virusIdx.add(new int[]{i, j, 0});
if (map[i][j] != 1) empty++;
}
}
recur(0, 0);
if (min != 1 << 30) System.out.println(min);
else System.out.println(-1);
}
}