📙 Algorithm Solving/Java
📙[Algo] 24.04.16 알고리즘
혜덕hyeduck
2024. 4. 17. 15:16
알고리즘 문제) BOJ 7569. 토마토
문제 요약
- M*N크기의 격자가 H개만큼 쌓여 있음
- 익은 토마토의 상, 하, 좌, 우, 앞, 뒤에있는 방향의 토마토는 영향을 받음
- 이때 모든 토마토들이 며칠이 지나야 다 익는지 최소 일수 구하기
시간 제한
- 1초
입력
- 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H
- M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수
- 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100
- 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다
- 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸
- 이러한 N개의 줄이 H번 반복하여 주어진
출력
- 토마토가 모두 익을 때까지 최소 며칠이 걸리는지 출력
- 장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int M, N, H;
static int[][][] box;
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int[] delH = {-1, 1};
static boolean[][][] visited;
static Queue<Node> q = new LinkedList<>();
static int tomatoCnt;
static int answer;
static class Node {
int height;
int row;
int col;
Node(int height, int row, int col) {
this.height = height;
this.row = row;
this.col = col;
}
}
static void bfs() {
int size, ch, cr, cc, mh, mr, mc;
while (!q.isEmpty()) {
size = q.size();
if (tomatoCnt == 0) return;
for (int i = 0; i < size; i++) {
ch = q.peek().height;
cr = q.peek().row;
cc = q.poll().col;
// 상하좌우
for (int dir = 0; dir < 4; dir++) {
mr = cr + delR[dir];
mc = cc + delC[dir];
if (mr < 0 || mc < 0 || N <= mr || M <= mc) continue;
if (visited[ch][mr][mc] || box[ch][mr][mc] != 0) continue;
q.offer(new Node(ch, mr, mc));
visited[ch][mr][mc] = true;
box[ch][mr][mc] = 1;
tomatoCnt--;
}
// 앞뒤
for (int dir = 0; dir < 2; dir++) {
mh = ch + delH[dir];
if (mh < 0 || H <= mh) continue;
if (visited[mh][cr][cc] || box[mh][cr][cc] != 0) continue;
q.offer(new Node(mh, cr, cc));
visited[mh][cr][cc] = true;
box[mh][cr][cc] = 1;
tomatoCnt--;
}
}
answer++;
}
}
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());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
box = new int[H][N][M];
visited = new boolean[H][N][M];
for (int i = 0; i < H; i++) {
for (int j = 0; j < N; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 0; k < M; k++) {
box[i][j][k] = Integer.parseInt(st.nextToken());
if (box[i][j][k] == 1){
q.offer(new Node(i, j, k));
visited[i][j][k] = true;
} else if (box[i][j][k] == 0) {
// 안익은 토마토 개수 세기
tomatoCnt++;
}
}
}
}
if (tomatoCnt == 0) {
bw.write("0");
} else {
bfs();
if (tomatoCnt > 0) bw.write("-1");
else bw.write(String.valueOf(answer));
}
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1647. 도시 분할 계획
문제 요약
- 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다
- 양방향(무방향) 간선
- 임의의 두 집 사이에 경로가 항상 존재
- 아래 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다
- 두 개의 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할
- 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다
- 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다
시간 제한
- 2초
입력
- 집의 개수 N, 길의 개수 M
- N은 2이상 10만이하인 정수
- M은 1이상 100만이하인 정수
- M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어짐
- A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)
출력
- 없애고 남은 길 유지비의 합의 최솟값을 출력
접근법
- MST구하고, 거기서 가장 간선이 큰 애를 하나 제거
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
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;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new int[M][3];
int v1, v2, c;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
graph[i][0] = v1;
graph[i][1] = v2;
graph[i][2] = c;
}
Arrays.sort(graph, new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2) {
return o1[2] - o2[2];
}
});
parent = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
parent[i] = i;
}
int answer = 0;
int max = 0;
for (int i = 0; i < M; i++) {
v1 = graph[i][0];
v2 = graph[i][1];
c = graph[i][2];
if (find(v1) == find(v2)) continue;
union(v1, v2);
answer += c;
max = Math.max(max, c);
}
bw.write(String.valueOf(answer - max));
bw.flush();
bw.close();
br.close();
}
}