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

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

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

난이도 : 골드 4

 

맵을 나눠 90도로 회전하는 것이 헷갈렸습니다. 종이에 적어가며 푸니 쉽게 이해가 됐네요.

정답을 구할 때 dfs를 이용하여 칸 수를 세주며 총얼음의 양을 구했습니다.

---

전역 변수

int n = 맵 크기의 지수(2^n)

int size = 맵 크기

int map[][] = 문제에서 주어진 값

int dx[], dy[] = 좌표를 이동하기 위한 배열

int sum = 총 얼음의 양

 

메소드

void main

입력을 받고 명령어에 적절히 동작합니다.

동작이 끝나면 얼음의 양, 칸 수를 세줍니다.

(rotate, melt, answer 호출)

 

void rotate

명령어의 숫자 크기만큼의 배열을 시계 방향으로 90도 돌려줍니다. 현재 배열에서 돌렸을 때의 값을 next배열에 저장했습니다. 회전이 끝났을 때 map은 next를 참조하도록 했습니다.

저 한 줄을 작성하는데 꽤 오랜 시간이 걸렸네요.

 

void melt

3면 이상이 얼음이 아닌 칸을 녹입니다. 이때 동시에 얼음이 녹으므로 적절한 처리를 해주지 않을 시 한 칸이 녹아야 하는데 모든 칸이 녹을 수 있는 대참사가 벌어질 수 있습니다. 

저는 오동작 방지를 위해 큐를 이용했습니다.

 

boolean check

파라미터로 받은 좌표값들이 정상 범위인지 확인합니다.

 

int answer

연결된 얼음들을 찾습니다. 연결된 얼음들의 칸 수를 세고 반환합니다.

얼음의 칸을 세며 총얼음의 양을 구하기 위해 sum에 더해줍니다.

(check 호출)

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	public class p20058 {
	static int n, size, sum, map[][];
	static int dx[] = {-1,0,0,1};
	static int dy[] = {0,1,-1,0};
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer stz = new StringTokenizer(br.readLine());
	n = Integer.parseInt(stz.nextToken());
	int q = Integer.parseInt(stz.nextToken());
	size = (int) Math.pow(2, n);
	map = new int[size][size];
	for(int i = 0; i < size; i++) {
	stz = new StringTokenizer(br.readLine());
	for(int j = 0; j < size; j++)
	map[i][j] = Integer.parseInt(stz.nextToken());
	}
	stz = new StringTokenizer(br.readLine());
	for(int i = 0; i < q; i++) {
	int l = Integer.parseInt(stz.nextToken());
	rotate(l);
	melt();
	}
	boolean visit[][] = new boolean[size][size];
	int max = 0;
	for(int i = 0; i < size; i++) {
	for(int j = 0; j < size; j++) {
	if(!visit[i][j] && map[i][j] > 0) {
	visit[i][j] = true;
	max = Math.max(max, answer(i, j, visit));
	}
	}
	}
	System.out.println(sum + "\n" + max);
	}
	public static void rotate(int l) {
	int loop = size / (int) Math.pow(2, l);
	int next[][] = new int[size][size];
	int x = 0;
	//세로 덩어리
	for(int i = 0; i < loop; i++) {
	int y = 0;
	if(i != 0)
	x += (int) Math.pow(2, l);
	//작은 덩어리
	for(int j = 0; j < loop; j++) {
	if(j != 0)
	y += (int) Math.pow(2, l);
	for(int a = 0; a < (int) Math.pow(2, l); a++) {
	for(int b = 0; b < (int) Math.pow(2, l); b++) {
	next[x+b][y-a+(int)Math.pow(2, l)-1] = map[x+a][y+b];
	}
	}
	}
	}
	map = next;
	}
	public static void melt() {
	Queue<Integer> qx = new LinkedList<>();
	Queue<Integer> qy = new LinkedList<>();
	for(int i = 0; i < size; i++) {
	for(int j = 0; j < size; j++) {
	int count = 0;
	for(int k = 0; k < 4; k++) {
	int nx = i + dx[k];
	int ny = j + dy[k];
	if(check(nx, ny))
	if(map[nx][ny] >= 1)
	count++;
	}
	if(count < 3) {
	qx.offer(i);
	qy.offer(j);
	}
	}
	}
	while(!qx.isEmpty()) {
	int x = qx.poll();
	int y = qy.poll();
	map[x][y]--;
	}
	}
	public static boolean check(int x, int y) {
	return x >= 0 && y >= 0 && x < size && y < size;
	}
	public static int answer(int x, int y, boolean visit[][]) {
	int count = 1;
	sum += map[x][y];
	for(int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if(check(nx, ny) && map[nx][ny] > 0 && !visit[nx][ny]) {
	visit[nx][ny] = true;
	count += answer(nx, ny, visit);
	}
	}
	return count;
	}
	}

view raw p20058.java hosted with ❤ by GitHub