난이도
골드4
문제
https://www.acmicpc.net/problem/20058
풀이
문제 풀이
1. 부분 격자 시계 방향 90도 회전
2. 특정 칸에 인접해있는 얼음칸이 3개 미만이라면 그 특정칸의 얼음을 녹인다.
3. 위의 과정을 Q만큼 반복
4. 남아있는 얼음의 합과 가장 큰 덩어리가 차지하는 칸의 개수를 구한다
상세 설명
1. 부분 격자 시계 방향 90도 회전
시계 방향으로 배열을 회전하는 방법에 대해 알지 못했다.
배열의 규칙을 직접 그려보며 방법을 차근차근 생각해내도록 하자.
위의 예시는 배열을 90도 시계 방향 회전했을 때의 예시이다.
주어진 문제는 격자를 부분적으로 구현해야했기 때문에 위의 규칙을 응용해서 풀었다.
public static int[][] divide(int L) {
int[][] tmp = new int[n][n];
L = (int) Math.pow(2, L);
for (int i = 0; i < n; i += L) {
for (int j = 0; j < n; j += L) {
rotate(i, j, L, tmp);
}
}
return tmp;
}
public static void rotate(int x, int y, int L, int[][] tmp) {
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
tmp[x + i][y + j] = map[x + L - 1 - j][y + i];
}
}
}
2. 특정 칸에 인접해 있는 얼음칸이 3개 미만이라면 그 특정칸의 얼음을 녹인다.
부분 격자를 회전완료했으면 모든 얼음칸의 주위를 확인하고 인접 얼음칸이 3개 미만이면 얼음을 녹여야한다.
여기서 주의할 점은 map을 복제해서 tmp라는 배열을 생성해 사용했다.
그 이유는 얼음은 한번에 녹아야하는데 map에 일일이 얼음 녹은걸 반영한다면 결과가 맞지 않기 때문이다.
public static int[][] melt() {
int[][] tmp = new int[n][n];
for (int i = 0; i < n; i++) {
tmp[i] = Arrays.copyOf(map[i], n);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cnt = 0;
if (map[i][j] == 0)
continue;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (map[nx][ny] > 0) {
cnt++;
}
}
}
if (cnt < 3)
tmp[i][j]--;
}
}
return tmp;
}3. 위의 과정을 Q만큼 반복
4. 남아있는 얼음의 합과 가장 큰 덩어리가 차지하는 칸의 개수를 구한다.
bfs를 사용해서 가장 큰 덩어리의 칸 개수를 구하면 된다.
로직을 수행하면서 총 얼음의 합도 함께 구해줬다.
public static void biggest() {
Queue<int[]> q = new LinkedList<>();
boolean[][] visit = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
totalIce += map[i][j];
if (map[i][j] > 0 && !visit[i][j]) {
q.add(new int[]{i, j});
visit[i][j] = true;
int cnt = 1;
while (!q.isEmpty()) {
int[] t = q.poll();
int tx = t[0];
int ty = t[1];
for (int k = 0; k < 4; k++) {
int nx = tx + dx[k];
int ny = ty + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (map[nx][ny] > 0 && !visit[nx][ny]) {
visit[nx][ny] = true;
q.add(new int[]{nx, ny});
cnt++;
}
}
}
}
land = Math.max(land, cnt);
}
}
}
}코드
import java.io.*;
import java.util.*;
public class BOJ20058 {
public static int n, q;
public static int[][] map;
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static int land, totalIce;
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());
q = Integer.parseInt(st.nextToken());
n = (int) Math.pow(2, n);
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());
int[] L = new int[q];
for (int i = 0; i < q; i++) {
L[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < q; i++) {
// 파이어스톰 시전
map = divide(L[i]);// 회전
map = melt();// 얼음 녹이기
}
land = totalIce = 0;
biggest();
System.out.println(totalIce);
System.out.println(land);
}
public static int[][] divide(int L) {
int[][] tmp = new int[n][n];
L = (int) Math.pow(2, L);
for (int i = 0; i < n; i += L) {
for (int j = 0; j < n; j += L) {
rotate(i, j, L, tmp);
}
}
return tmp;
}
public static void rotate(int x, int y, int L, int[][] tmp) {
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
tmp[x + i][y + j] = map[x + L - 1 - j][y + i];
}
}
}
public static int[][] melt() {
int[][] tmp = new int[n][n];
for (int i = 0; i < n; i++) {
tmp[i] = Arrays.copyOf(map[i], n);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cnt = 0;
if (map[i][j] == 0)
continue;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (map[nx][ny] > 0) {
cnt++;
}
}
}
if (cnt < 3)
tmp[i][j]--;
}
}
return tmp;
}
public static void biggest() {
Queue<int[]> q = new LinkedList<>();
boolean[][] visit = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
totalIce += map[i][j];
if (map[i][j] > 0 && !visit[i][j]) {
q.add(new int[] { i, j });
visit[i][j] = true;
int cnt = 1;
while (!q.isEmpty()) {
int[] t = q.poll();
int tx = t[0];
int ty = t[1];
for (int k = 0; k < 4; k++) {
int nx = tx + dx[k];
int ny = ty + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (map[nx][ny] > 0 && !visit[nx][ny]) {
visit[nx][ny] = true;
q.add(new int[] { nx, ny });
cnt++;
}
}
}
}
land = Math.max(land, cnt);
}
}
}
}
(참고)
https://velog.io/@yul_00/Java-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%ED%9A%8C%EC%A0%84-xf2gjagw
https://skdltm117.tistory.com/32
Back-End Developer