알고리즘(백준 등) 공부/백준(자바)
백준 1355번: 구멍난 케이크 자르기
posite
2026. 4. 5. 15:31
https://www.acmicpc.net/problem/1355
원점을 중심으로 정사각형으로 뚤려있는 정사각형의 케이크를 가로, 세로로 자를 때 케이크의 조각의 수를 구하는 문제이다. 절단선이 구멍을 지날 때는 케이크가 쪼개지지 않습니다. 구멍 양옆에 붙어있는 케이크들만 각각 분리되어 상당히 복잡하다.
좌표가 실수로 주어지므로, 우리는 유의미한 좌표들만 모아 평면을 격자(Grid)로 쪼개야 한다. X축 기준선, Y축 기준선을 기준으로 분할한다. -> X축 기준선: LC, -LH, LH, LC + 입력받은 모든 세로 절단선, Y축 기준선: LC, -LH, LH, LC + 입력받은 모든 가로 절단선
이를 중복 없이 정렬된 상태로 저장하기 위해 TreeSet을 이용하였으며 모든 기준선들을 배열로 만들었다.
TreeSet<Double> xSet = new TreeSet<>();
TreeSet<Double> ySet = new TreeSet<>();
double[] bounds = {-LC, -LH, LH, LC};
for (double b : bounds) {
xSet.add(b);
ySet.add(b);
}
int H = Integer.parseInt(br.readLine());
double[] hLines = new double[H];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < H; i++) {
hLines[i] = Double.parseDouble(st.nextToken());
if (hLines[i] >= -LC && hLines[i] <= LC) {
ySet.add(hLines[i]);
}
}
int V = Integer.parseInt(br.readLine());
double[] vLines = new double[V];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < V; i++) {
vLines[i] = Double.parseDouble(st.nextToken());
if (vLines[i] >= -LC && vLines[i] <= LC) {
xSet.add(vLines[i]);
}
}
br.close();
double[] sx = xSet.stream().mapToDouble(Double::doubleValue).toArray();
double[] sy = ySet.stream().mapToDouble(Double::doubleValue).toArray();
이후, 각각의 영역이 케이크인지 아닌지를 구분한다. LC 안에 있고, LH 영역 밖에 있다면 케이크이다.
int rows = sy.length - 1;
int cols = sx.length - 1;
boolean[][] isCake = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
double mx = (sx[j] + sx[j + 1]) / 2.0;
double my = (sy[i] + sy[i + 1]) / 2.0;
if (Math.abs(mx) <= LC + EPS && Math.abs(my) <= LC + EPS) {
if (!(Math.abs(mx) < LH - EPS && Math.abs(my) < LH - EPS)) {
isCake[i][j] = true;
}
}
}
}
마지막으로, BFS로 영역들을 방문하면서 영역의 갯수를 센다. 경계선은 통과하지 못하게 한다.
boolean[][] visited = new boolean[rows][cols];
int pieces = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (isCake[i][j] && !visited[i][j]) {
pieces++;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{i, j});
visited[i][j] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || !isCake[nr][nc] || visited[nr][nc]) {
continue;
}
double line;
boolean blocked = false;
if (d == 0) {
line = sy[r];
for (double h : hLines) {
if (Math.abs(h - line) < EPS) {
blocked = true;
break;
}
}
} else if (d == 1) {
line = sy[r + 1];
for (double h : hLines) {
if (Math.abs(h - line) < EPS) {
blocked = true;
break;
}
}
} else if (d == 2) {
line = sx[c];
for (double v : vLines) {
if (Math.abs(v - line) < EPS) {
blocked = true;
break;
}
}
} else {
line = sx[c + 1];
for (double v : vLines) {
if (Math.abs(v - line) < EPS) {
blocked = true;
break;
}
}
}
if (!blocked) {
visited[nr][nc] = true;
q.add(new int[]{nr, nc});
}
}
}
}
}
}
최종 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class 구멍난케이크자르기1355 {
static final double EPS = 1e-9;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
double LC = Double.parseDouble(st.nextToken());
double LH = Double.parseDouble(st.nextToken());
TreeSet<Double> xSet = new TreeSet<>();
TreeSet<Double> ySet = new TreeSet<>();
double[] bounds = {-LC, -LH, LH, LC};
for (double b : bounds) {
xSet.add(b);
ySet.add(b);
}
int H = Integer.parseInt(br.readLine());
double[] hLines = new double[H];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < H; i++) {
hLines[i] = Double.parseDouble(st.nextToken());
if (hLines[i] >= -LC && hLines[i] <= LC) {
ySet.add(hLines[i]);
}
}
int V = Integer.parseInt(br.readLine());
double[] vLines = new double[V];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < V; i++) {
vLines[i] = Double.parseDouble(st.nextToken());
if (vLines[i] >= -LC && vLines[i] <= LC) {
xSet.add(vLines[i]);
}
}
br.close();
double[] sx = xSet.stream().mapToDouble(Double::doubleValue).toArray();
double[] sy = ySet.stream().mapToDouble(Double::doubleValue).toArray();
int rows = sy.length - 1;
int cols = sx.length - 1;
boolean[][] isCake = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
double mx = (sx[j] + sx[j + 1]) / 2.0;
double my = (sy[i] + sy[i + 1]) / 2.0;
if (Math.abs(mx) <= LC + EPS && Math.abs(my) <= LC + EPS) {
if (!(Math.abs(mx) < LH - EPS && Math.abs(my) < LH - EPS)) {
isCake[i][j] = true;
}
}
}
}
boolean[][] visited = new boolean[rows][cols];
int pieces = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (isCake[i][j] && !visited[i][j]) {
pieces++;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{i, j});
visited[i][j] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || !isCake[nr][nc] || visited[nr][nc]) {
continue;
}
double line;
boolean blocked = false;
if (d == 0) {
line = sy[r];
for (double h : hLines) {
if (Math.abs(h - line) < EPS) {
blocked = true;
break;
}
}
} else if (d == 1) {
line = sy[r + 1];
for (double h : hLines) {
if (Math.abs(h - line) < EPS) {
blocked = true;
break;
}
}
} else if (d == 2) {
line = sx[c];
for (double v : vLines) {
if (Math.abs(v - line) < EPS) {
blocked = true;
break;
}
}
} else {
line = sx[c + 1];
for (double v : vLines) {
if (Math.abs(v - line) < EPS) {
blocked = true;
break;
}
}
}
if (!blocked) {
visited[nr][nc] = true;
q.add(new int[]{nr, nc});
}
}
}
}
}
}
System.out.print(pieces);
}
}