https://www.acmicpc.net/problem/20058
20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
와 두번다시는 풀고 싶지는 않는문제네요
* 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
->3개 미만은 얼음이 줄어든다 (무슨 국어 문제인가.. ㅎ)
* 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합
->연결된 얼음 덩어리들의 칸의 갯수의 합,즉 얼음은 bfs,dfs를 통해서 연결해서 얼음 덩어리들을 계산하라는 의미
import java.util.*;
import java.io.*;
import java.lang.*;
import java.io.*;
public class Main {
public static int n;
public static int q;
public static int maps[][];
public static int copyMaps[][];
public static boolean bCheck[][];
public static boolean initbCheck[][];
public static boolean[][] visited;
public static int L;
public static void prints(int tmpMap[][]){
System.out.println();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(tmpMap[i][j]+",");
}
System.out.println();
}
}
public static class Ice {
public int i;
public int j;
public Ice(int i,int j) {
this.i=i;
this.j=j;
}
}
public static void Rotation(int starti, int startj){
int cnt=1;
int rStarti=starti*L;
int rEndi=starti*L+L;
int rStartj=startj*L;
int rEndj=startj*L+L;
int rLengthI=(rStarti+rEndi)/2;
int rLengthJ=(rStartj+rEndj)/2;
int rCountI=(rEndi-rStarti)/2;
int rCountJ=(rEndi-rStarti)/2;
//1 ->2
for(int i=rStarti;i<rLengthI;i++){
for(int j=rStartj;j<rLengthJ;j++){
copyMaps[i][j+ rCountJ]=maps[i][j];
}
}
//2->3
for(int i=rStarti;i<rLengthI;i++){
for(int j=rLengthJ;j<rEndj;j++){
copyMaps[i+rCountI][j]=maps[i][j];
}
}
//3->4
for(int i=rLengthI;i<rEndi;i++){
for(int j=rLengthJ ;j<rEndj;j++){
copyMaps[i][j-rCountJ]=maps[i][j];
}
}
//4->1
for(int i=rLengthI;i<rEndi;i++){
for(int j=rStartj;j<rLengthJ;j++){
copyMaps[i-rCountI][j]=maps[i][j];
}
}
//prints(copyMaps);
}
public static void Rotations(int starti, int startj) {
int rStarti = starti * L;
int rStartj = startj * L;
int[][] temp = new int[L][L];
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
temp[j][L - 1 - i] = maps[rStarti + i][rStartj + j];
}
}
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
maps[rStarti + i][rStartj + j] = temp[i][j];
}
}
}
public static int bfs(int x, int y) {
if(maps[x][y] <= 0) return 0;
int count = 1;
Queue<Ice> queue = new LinkedList<>();
queue.add(new Ice(x, y));
visited[x][y] = true;
while (!queue.isEmpty()) {
Ice current = queue.poll();
int i = current.i;
int j = current.j;
int[] di = {-1, 1, 0, 0};
int[] dj = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni >= 0 && ni < n && nj >= 0 && nj < n && !visited[ni][nj] && maps[ni][nj] > 0) {
queue.add(new Ice(ni, nj));
visited[ni][nj] = true;
count++;
}
}
}
return count;
}
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
q=scan.nextInt();
double tmpn=Math.pow(2,n);
n=(int)tmpn;
maps=new int[n][n];
copyMaps=new int[n][n];
bCheck=new boolean[n][n];
initbCheck=new boolean[n][n];
visited = new boolean[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
maps[i][j]=scan.nextInt();
copyMaps[i][j]=maps[i][j];
}
}
for(int t=0;t<q;t++){
L=scan.nextInt();
double tmpL=Math.pow(2,L);
L=(int)tmpL;
//2x2
//4x4
//8x8
int divide=n/L;
for(int i=0;i<divide;i++){
for(int j=0;j<divide;j++){
Rotations(i,j);
}
}
int diri[]= {-1,1,0,0};
int dirj[]= {0,0,-1,1};
ArrayList<Ice> saveIce=new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int iceCnt = 0;
for (int k = 0; k < 4; k++) {
int ni = i + diri[k];
int nj = j + dirj[k];
if (ni < 0 || nj < 0 || ni >= n || nj >= n) continue;
if (maps[ni][nj] > 0) iceCnt++;
}
if (iceCnt < 3) {
saveIce.add(new Ice(i, j));
}
}
}
// 저장된 모든 칸의 얼음을 1 줄입니다.
for (Ice ice : saveIce) {
maps[ice.i][ice.j] = Math.max(0, maps[ice.i][ice.j] - 1);
}
}
int sum=0;
int maxs=0;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(maps[i][j]>=0) {
sum+=maps[i][j];
}
}
}
System.out.println(sum);
int maxSizeOfIce = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && maps[i][j] > 0) {
maxSizeOfIce = Math.max(maxSizeOfIce, bfs(i, j));
}
}
}
System.out.println(maxSizeOfIce);
//Rotation(0,1);
}
}'알고리즘 공부' 카테고리의 다른 글
| 백준 - 감시 (0) | 2024.04.04 |
|---|---|
| 백준 배열과 연산 (0) | 2024.04.04 |
| 백준 마법사 상어와 토네이도 (0) | 2024.04.02 |
| 백준 최소 회의실 개수 (0) | 2024.04.02 |
| 백준 배열돌리기2 (0) | 2024.04.02 |