Baekjoon 20058 - 마법사 상어와 파이어스톰 (클릭 시 이동)
문제
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.
파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.
마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.
- 남아있는 얼음 A[r][c]의 합
- 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 3982 | 1697 | 1069 | 39.229% |
입력
첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.
마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.
출력
첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.
#### 풀이
- 배열을 알맞게 회전시킨다(1회).
- 회전시킨 후 주변에 얼음이 2개 이하인(값이 0인) 얼음을 찾아 녹인다(1을 뺀다.)
- 이후 1,2 과정을 Q만큼 반복한다.
- 가장 큰 얼음덩어리를 찾음과 동시에 전체 얼음의 수를 구한다.
과정
1. 배열을 알맞게 회전시킨다.
배열을 L의 크기에 맞게 회전시키기 위한 메서드을 구현한다.
회전 시킬 시작좌표 (r,c)와 L, 그리고 회전시킨 후의 배열을 저장할 temp를 파라미터로 받는다.
배열A의 각 행을 새로운 배열의 가장 오른쪽 열부터 크기에 맞게 채워 넣는다.
static void rotate(int r, int c, int L, int[][] temp) {
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
temp[r + j][c + L - i - 1] = A[r + i][c + j];
}
}
}이 메소드를 모든 배열에 수행하기 위한 메서드를 구현한다.
A와 같은 크기의 새로운 배열을 생성하고
2^L 크기만큼 쪼개서 배열을 회전시키므로 그 값을 rotate의 파라미터로 넣어주게 된다.
배열의 시작위치를 지정하기 위한 2중 for문으로, 증감식이 i = i + L이 된다.
static int[][] divide(int L) {
int[][] temp = 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, temp);
}
}
return temp;
}2. 회전시킨 후 주변에 얼음이 2개 이하인(값이 0인) 얼음을 찾아 녹인다(1을 뺀다.)
얼음은 동시에 녹아야 한다.
이 말은 즉, 얼음이 녹은걸 다음위치에서 반영시키면 안된다.
따라서 새로운 배열을 만들어서 반영된 값을 저장 해 두어야 한다.
예를들어 인접한 얼음이 1,3이라는 값을 가지고 있을 때
1이 녹으면 0,3이 되므로 3의 위치에서 얼음의 갯수를 탐색할때 얼음이 1개 적어지므로 0,2가 될 수 있을것이다.
이러한 부분을 방지하기 위해 새로운 배열을 선언해야한다.
static int[][] melt() {
//녹은 얼음의 값을 저장할 배열 선언.
int[][] temp = new int[N][N];
for (int i = 0; i < N; i++)
temp[i] = Arrays.copyOf(A[i], N);
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int cnt = 0;
if (A[r][c] == 0)
continue;
// 주변 얼음의 갯수 세기
for (int i = 0; i < 4; i++) {
int nr = r + deltas[i][0];
int nc = c + deltas[i][1];
if (isIn(nr, nc) && A[nr][nc] > 0) {
cnt++;
}
}
// 3개보다 적으면 얼음 녹이기.
if (cnt < 3) {
temp[r][c]--;
}
}
}
return temp;
}3. 가장 큰 얼음덩어리를 찾음과 동시에 전체 얼음의 수를 구한다.
BFS를 수행하여 모든 인접한 얼음을 방문하여 갯수를 세고(land)
그 값을 totalIce에 더해준다.
land는 가장 큰 것을 찾아야 하므로 한번의 BFS가 끝나면 비교하여 더 큰 값을 반영한다.
static void findBiggest() {
boolean[][] visited = new boolean[N][N];
Stack<int[]> stack = new Stack<>();
land = 0;
totalIce = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A[i][j] > 0 && !visited[i][j]) {
stack.push(new int[] { i, j });
visited[i][j] = true;
totalIce += A[i][j];
int count = 1;
while (!stack.isEmpty()) {
int[] temp = stack.pop();
int r = temp[0];
int c = temp[1];
for (int k = 0; k < 4; k++) {
int nr = r + deltas[k][0];
int nc = c + deltas[k][1];
if (isIn(nr, nc) && A[nr][nc] > 0 && !visited[nr][nc]) {
count++;
visited[nr][nc] = true;
stack.push(new int[] { nr, nc });
totalIce += A[nr][nc];
}
}
}
land = Math.max(count, land);
}
}
}
}최종 소스코드
import java.io.*;
import java.util.*;
public class BJ_G4_20058 {
static int N, Q, land, totalIce;
static int[][] A;
static int[] L;
static int[][] deltas = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static StringTokenizer st;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
N = (int) Math.pow(2, N);
A = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
L = new int[Q];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < Q; i++) {
L[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < Q; i++) {
A = divide(L[i]);
A = melt();
}
findBiggest();
System.out.println(totalIce);
System.out.println(land);
}
static int[][] divide(int L) {
int[][] temp = 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, temp);
}
}
return temp;
}
static void rotate(int r, int c, int L, int[][] temp) {
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
temp[r + j][c + L - i - 1] = A[r + i][c + j];
}
}
}
static int[][] melt() {
int[][] temp = new int[N][N];
for (int i = 0; i < N; i++) {
temp[i] = Arrays.copyOf(A[i], N);
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int cnt = 0;
if (A[r][c] == 0)
continue;
for (int i = 0; i < 4; i++) {
int nr = r + deltas[i][0];
int nc = c + deltas[i][1];
if (isIn(nr, nc) && A[nr][nc] > 0) {
cnt++;
}
}
if (cnt < 3) {
temp[r][c]--;
}
}
}
return temp;
}
static void findBiggest() {
boolean[][] visited = new boolean[N][N];
Stack<int[]> stack = new Stack<>();
land = 0;
totalIce = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A[i][j] > 0 && !visited[i][j]) {
stack.push(new int[] { i, j });
visited[i][j] = true;
totalIce += A[i][j];
int count = 1;
while (!stack.isEmpty()) {
int[] temp = stack.pop();
int r = temp[0];
int c = temp[1];
for (int k = 0; k < 4; k++) {
int nr = r + deltas[k][0];
int nc = c + deltas[k][1];
if (isIn(nr, nc) && A[nr][nc] > 0 && !visited[nr][nc]) {
count++;
visited[nr][nc] = true;
stack.push(new int[] { nr, nc });
totalIce += A[nr][nc];
}
}
}
land = Math.max(count, land);
}
}
}
}
static boolean isIn(int r, int c) {
return r >= 0 && r < N && c >= 0 && c < N;
}
}
'Algorithm > BaekJoon' 카테고리의 다른 글
| [백준] 17143번 - 낚시왕 (java) (0) | 2021.10.02 |
|---|---|
| [백준] 14503번 - 로봇 청소기 (java) (0) | 2021.09.25 |
| [백준] 17144번 - 미세먼지 안녕! (java) (0) | 2021.09.24 |
| [백준] 1715번 - 카드 정렬하기 (java) (0) | 2021.09.22 |
| [백준] 1932번 - 정수 삼각형 (java) (0) | 2021.09.21 |
