[백준] G4 20058 마법사 상어와 파이어스톰 (java)

https://www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰

 

풀이

 

1) 마법사 상어가 시전한 단계 L 에 따라 배열을 구간별로 나눈다.

2) 나눌 수 있는 모든 케이스에서 다음 과정을 할 것이다.

2-1) 나눠진 원본 배열을 temp[][]배열에 복사한다.

3) temp[][] 배열을 시계방향으로 90도 회전한 후 원본 배열에 집어넣는다.

4) bfs를 돌아 4방에 얼음이 없거나 장외인 경우가 3칸 이상일 경우 A[r][c] 1 감소

5) 마법사 상어의 마법이 모두 끝나면 남아 있는 얼음의 합과 가장큰 덩어리의 칸수 출력.

 

주의사항

 

1) "이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다." <-설명이 거지 같다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G4_20058_마법사상어와파이어스톰 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,Q,P, map[][], temp[][],remainIce,maxIceberg;
	static boolean isVisited[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		
		N = Integer.parseInt(tokens.nextToken());
		Q = Integer.parseInt(tokens.nextToken());
		P = (int) Math.pow(2, N);
		map = new int[P][P];
		isVisited = new boolean[P][P];
		for(int r=0; r<P; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<P; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
				remainIce += map[r][c];
			}	
		}
		tokens = new StringTokenizer(input.readLine());
		for(int q=0; q<Q; q++) {
			int side = (int) Math.pow(2, Integer.parseInt(tokens.nextToken())); // 0이면 어쩐담?
			temp = new int[side][side];
			for(int r=0; r<P; r=r+side) {
				for(int c=0; c<P; c=c+side) {
					spinMap(r,c,side);
				}	
			}
			fireStorm();
		}
		if(remainIce > 0) {
			getMaxIceberg();
			System.out.println(remainIce);
			System.out.println(maxIceberg);
		}else {
			System.out.println(0);
			System.out.println(0);
		}
	}
	

	private static void getMaxIceberg() {
		for(int r=0; r<P; r++) {
			for(int c=0; c<P; c++) {
				if(!isVisited[r][c] && map[r][c] != 0) {
					bfs(r,c);
				}
			}	
		}
	}

	private static void bfs(int r, int c) {
		
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(r, c));
		isVisited[r][c] = true;
		int cnt = 1;
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && map[nr][nc] != 0) {
					isVisited[nr][nc] = true;
					queue.offer(new Node(nr, nc));
					cnt++;
				}
			}
		}
		if(maxIceberg < cnt) {
			maxIceberg = cnt;
		}
	}

	static class Node{
		int r;
		int c;
		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	
	private static void fireStorm() {
		temp = new int[P][P];
		int cnt;
		for(int r=0; r<P; r++) {
			for(int c=0; c<P; c++) {
				if(map[r][c] == 0) continue;
				temp[r][c] = map[r][c];
				cnt=0;
				for(int d=0; d<4; d++) {
					int nr = r + dr[d];
					int nc = c + dc[d];
					if(!isIn(nr, nc)) {
						cnt++;
					}else if(map[nr][nc] == 0) {
						cnt++;
					}
				}
				if(cnt >= 2) {
					temp[r][c]--;
					remainIce--;
				}
			}	
		}
		for(int r=0; r<P; r++) {
			for(int c=0; c<P; c++) {
				map[r][c] = temp[r][c];
			}	
		}
	}

	private static void spinMap(int curR, int curC, int side) {
		int tr,tc;
		tr=0;
		for(int r=curR; r<curR+side; r++) {
			tc=0;
			for(int c=curC; c<curC+side; c++) {
				temp[tr][tc] = map[r][c];
				tc++;
			}	
			tr++;
		}
		tr=0;
		for(int r=curR; r<curR+side; r++) {
			tc=0;
			for(int c=curC; c<curC+side; c++) {
				map[r][c] = temp[side-1-tc][tr];
				tc++;
			}	
			tr++;
		}
	}

	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<P && c<P);
	}
	
	static int dr[] = {0,1,0,-1};
	static int dc[] = {-1,0,1,0};

	static String src =
			"3 10\r\n"
			+ "1 0 3 4 5 6 7 0\r\n"
			+ "8 0 6 5 4 3 2 1\r\n"
			+ "1 2 0 4 5 6 7 0\r\n"
			+ "8 7 6 5 4 3 2 1\r\n"
			+ "1 2 3 4 0 6 7 0\r\n"
			+ "8 7 0 5 4 3 2 1\r\n"
			+ "1 2 3 4 5 6 7 0\r\n"
			+ "0 7 0 5 4 3 2 1\r\n"
			+ "1 2 3 1 2 3 1 2 3 1";
}

 

후기

 

 문제를 풀면서 가장 어려웠던 부분은 배열을 돌리는 것이다. 전체 배열을 돌리는 것은 쉬운데 격자로 나눠서 돌리는 것이 상당히 번거로웠다. 뭔가 다른 간단한 수학 계산으로 가능할 것 같았는데 머리가 안좋은 관계로 그런 마법의 공식은 찾지 못했다.

구글링을 해보니 내가 고민했던 마법의 공식을 찾은 사람이 있었다.

// 격자 시계방향 회전
void rotate(int y, int x, int L){
    for(int i=0;i<L;i++)
        for(int j=0;j<L;j++)
            temp[i][j]=board[y+L-1-j][x+i];
    for(int i=0;i<L;i++)
        for(int j=0;j<L;j++)
            board[y+i][x+j]=temp[i][j];
}

출처 : https://yjyoon-dev.github.io/boj/2020/11/04/boj-20058/

[BOJ][삼성기출] 백준 20058번 - 마법사 상어와 파이어스톰 풀이

배열돌리기는 자주 나오는 문제이므로 자주 보면서 익혀 놓아야겠다.