https://www.acmicpc.net/problem/20058
1. 아이디어
2차원 배열의 회전, 얼음의 양 줄이기, 가장 큰 얼음 덩어리의 크기를 각각 구현해서 합치면 되는 문제로 2차원 배열의 회전읜 격자의 크기와 동일한 크기의 배열과 인덱스의 활용으로, 얼음 양 줄이기는 Queue를 활용해서, 가장 큰 얼음 덩어리의 크기는 BFS, DFS 알고리즘으로 구할 수 있다.
2. 문제풀이
얼음판의 크기는 2^N으로 주어지는데 편의를 위해 N을 2^N으로 바꿔서 이용했다. 이를 위해 비트 연산자를 활용했다. 격자의 크기 역시 비트 연산으로 L을 2^L로 바뀌줬고 이후 회전 메서드에서 이용했다. 회전은 두 2차원 배열의 크기가 다른 점만 주의해서 구현하면 된다. 얼음의 양 줄이기는 사방탐색으로 줄여야 하는 위치만 Queue에 담아주고 이후 한번에 줄이도록 구현했다. BFS, DFS는 탐색한 얼음의 크기를 반환하면 된다.
3. 코드
import java.io.*;
import java.util.*;
public class Main_BFS {
private static final int[] dr = {-1, 0, 1, 0};
private static final int[] dc = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = 1 << Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
int[][] map = new int[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());
}
}
st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens()) {
int L = 1 << Integer.parseInt(st.nextToken());
int[][] tmp = new int[L][L];
for (int i = 0; i < N; i += L) {
for (int j = 0; j < N; j += L) {
rotate(i, j, i + L, j + L, L, map, tmp);
}
}
remove(N, map);
}
int sum = 0;
int max = 0;
boolean[][] visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum += map[i][j];
if (map[i][j] == 0 || visited[i][j]) continue;
int result = bfs(i, j, N, map, visited);
max = Math.max(max, result);
}
}
System.out.println(sum);
System.out.println(max);
}
private static void rotate(int r1, int c1, int r2, int c2, int L, int[][] map, int[][] tmp) {
for (int i = r1; i < r2; i++) {
for (int j = c1; j < c2; j++) {
tmp[(j - c1)][L - 1 - (i - r1)] = map[i][j];
}
}
for (int i = r1; i < r2; i++) {
for (int j = c1; j < c2; j++) {
map[i][j] = tmp[(i - r1)][(j - c1)];
}
}
}
private static void remove(int N, int[][] map) {
Queue<int[]> q = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) continue;
int cnt = 0;
for (int dir = 0; dir < 4; dir++) {
int nr = i + dr[dir];
int nc = j + dc[dir];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (map[nr][nc] > 0) cnt++;
}
if (cnt < 3) q.add(new int[]{i, j});
}
}
while (!q.isEmpty()) {
int[] node = q.remove();
map[node[0]][node[1]]--;
}
}
private static int bfs(int r, int c, int N, int[][] map, boolean[][] visited) {
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{r, c});
visited[r][c] = true;
int cnt = 0;
while (!q.isEmpty()) {
int[] node = q.remove();
cnt++;
for (int dir = 0; dir < 4; dir++) {
int nr = node[0] + dr[dir];
int nc = node[1] + dc[dir];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (map[nr][nc] == 0 || visited[nr][nc]) continue;
q.add(new int[]{nr, nc});
visited[nr][nc] = true;
}
}
return cnt;
}
}import java.io.*;
import java.util.*;
public class Main_DFS {
private static final int[] dr = {-1, 0, 1, 0};
private static final int[] dc = {0, 1, 0, -1};
private static int N;
private static int[][] map;
private static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = 1 << Integer.parseInt(st.nextToken());
int Q = Integer.parseInt(st.nextToken());
map = new int[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());
}
}
st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens()) {
int L = 1 << Integer.parseInt(st.nextToken());
int[][] tmp = new int[L][L];
for (int i = 0; i < N; i += L) {
for (int j = 0; j < N; j += L) {
rotate(i, j, i + L, j + L, L, tmp);
}
}
remove();
}
int sum = 0;
int max = 0;
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum += map[i][j];
if (map[i][j] == 0 || visited[i][j]) continue;
int result = dfs(i, j);
max = Math.max(max, result);
}
}
System.out.println(sum);
System.out.println(max);
}
private static void rotate(int r1, int c1, int r2, int c2, int L, int[][] tmp) {
for (int i = r1; i < r2; i++) {
for (int j = c1; j < c2; j++) {
tmp[(j - c1)][L - 1 - (i - r1)] = map[i][j];
}
}
for (int i = r1; i < r2; i++) {
for (int j = c1; j < c2; j++) {
map[i][j] = tmp[(i - r1)][(j - c1)];
}
}
}
private static void remove() {
Queue<int[]> q = new ArrayDeque<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) continue;
int cnt = 0;
for (int dir = 0; dir < 4; dir++) {
int nr = i + dr[dir];
int nc = j + dc[dir];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (map[nr][nc] > 0) cnt++;
}
if (cnt < 3) q.add(new int[]{i, j});
}
}
while (!q.isEmpty()) {
int[] node = q.remove();
map[node[0]][node[1]]--;
}
}
private static int dfs(int r, int c) {
visited[r][c] = true;
int cnt = 1;
for (int dir = 0; dir < 4; dir++) {
int nr = r + dr[dir];
int nc = c + dc[dir];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (map[nr][nc] == 0 || visited[nr][nc]) continue;
cnt += dfs(nr, nc);
}
return cnt;
}
}4. 후기
- BFS
- DFS
'코딩테스트 준비 > 백준' 카테고리의 다른 글
| [백준] 21611번 - 마법사 상어와 블리자드 [Java] (0) | 2025.02.23 |
|---|---|
| [백준] 14225번 - 부분수열의 합 [Java] (1) | 2025.02.21 |
| [백준] 17779번 - 게리맨더링 2 [Java] (0) | 2025.02.21 |
| [백준] 20920번 - 영단어 암기는 괴로워 [Java] (0) | 2025.02.20 |
| [백준] 20922번 - 겹치는 건 싫어 [Java] (0) | 2025.02.19 |
