[JAVA] 백준 20058 마법사 상어와 파이어스톰

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

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

 

1. 서론

 

헤매기는 했지만 이게 골3이라고? 싶은 문제.... 골3보단 쉬운 듯? 시뮬 + bfs 문제

 

2. 문제 풀이

 

배열을 돌리는게 좀 어려워서 그렇지 문제 자체는 되게 간단하다.

 

로직

 

1. 주어진 l에 따라서 범위를 나눠줌  //rangeCheck()

문제에 나온 것처럼 l = 1, l = 2...처럼 작게 범위를 나눠서 rotation함수로 그 값들을 넘겨준다

 

2. 나눠진 범위에 따라서 배열을 돌림 //rotation()

넘겨진 범위 안에서 배열을 돌려준다

 

3. 돌려진 배열에서 주변값을 탐색한 후에 -1 할지 말지 결정 // calc()

동서남북을 탐색하며 얼음이 3칸 보다 적다면 -1을 해준다

 

4. 주어진 l의 수만큼 1~3 반복

 

5. 다 구해진 배열의 얼음 총 합 구하기 // total

 

6. 얼음 덩어리 구하기 // bfs()

배열을 돌면서 얼음인 곳이 나오면 bfs 함수로 들어와서 방문 체크를 해주며 얼음인 곳만 큐에 넣어서 탐색했다. 이때 cnt를 해줬다.

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {
	
	static int n, q, r, c, s, max;
	static int[][] map;
	static int[] l, dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
	static boolean[][] visit;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		q = Integer.parseInt(st.nextToken());
		
		s = (int)Math.pow(2, n);
		map = new int[s][s];
		
		for (int i = 0; i < s; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < s; j++)
				map[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++) {
			rangeCheck((int)Math.pow(2, l[i]));
			calc();
		}
		
		visit = new boolean[s][s];
		int total = 0;
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				total += map[i][j];
				if (map[i][j] > 0 && !visit[i][j])
					bfs(i, j);
			}
		}
		
		System.out.println(total + "\n" + max);
	}
	
	public static void bfs(int x, int y) {
		Queue<Point> q = new LinkedList<>();
		
		visit[x][y] = true;
		q.add(new Point(x, y));
		
		int cnt = 1;
		while (!q.isEmpty()) {
			Point p = q.poll();
			
			for (int k = 0; k < 4; k++) {
				int nx = p.x + dx[k], ny = p.y + dy[k];
				if (range(nx, ny) && !visit[nx][ny]) {
					visit[nx][ny] = true;
					if (map[nx][ny] > 0) {
						q.add(new Point(nx, ny));
						cnt++;
					}		
				}
			}
		}
		
		max = Math.max(max, cnt);
	}
	
	public static void calc() {
		int[][] tmp = new int[s][s];
		copy(tmp, map);
		
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				int cnt = 0;
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k], ny = j + dy[k];
					if (range(nx, ny) && map[nx][ny] > 0)
						cnt++;
				}
				if (cnt < 3) {
					tmp[i][j]--;
					if (tmp[i][j] < 0)
						tmp[i][j] = 0;
				}
			}
		}
		
		copy(map, tmp);
	}
	
	public static void rangeCheck(int r) {
		int x1 = 0, x2 = r, y1 = 0, y2 = r;
		while (true) {
			rotation(x1, x2, y1, y2, r);
			
			if (x2 == s && y2 == s) break;
			y1 += r;
			y2 += r;
			
			if (y2 > s && x2 != s) {
				y2 = r; y1 = 0;
				x1 += r; x2 += r;
			}
		}
	}
	
	public static void rotation(int x1, int x2, int y1, int y2, int r) {
		int[][] tmp = new int[r][r];
		int[][] tmap = new int[r][r];
		
		int x = 0, y = 0;
		for (int i = x1; i < x2; i++) {
			for (int j = y1; j < y2; j++)
				tmap[x][y++] = map[i][j];
			x++; y = 0;
		}
		
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < r; j++)
				tmp[i][j] = tmap[r - 1 - j][i];
		}
		
		x = 0; y = 0;
		for (int i = x1; i < x2; i++) {
			for (int j = y1; j < y2; j++)
				map[i][j] = tmp[x][y++];
			x++; y = 0;
		}
	}
	
	public static void copy (int[][] a, int[][] b) {
		for (int i = 0 ; i < s; i++)
			for (int j = 0; j < s; j++)
				a[i][j] = b[i][j];
	}
	
	public static boolean range(int nx, int ny) {
		if (nx >= 0 && nx < s && ny >= 0 && ny < s)
			return true;
		return false;
	}
}

 

사실 어쩌면 배열을 범위별로 쪼개서 돌리는 게 제일 핵심 포인트인데 사람들 보면 막 재귀하고 어쩌고 복잡하게 짜던데 나는 도저히 그럴 여력이... 능력이 없어서 원시적인 방법으로 구현했다.

 

쪼개야 하는 범위의 크기만큼 배열 두 개를 만들어서 한 개에는 원래 배열의 값을 복사하고 나머지 한 개에는 원래 배열을 복사한 값을 이용해 90도 돌린 값을 적는다. 굳이 이렇게 한 이유는 원래의 배열을 가져다가 범위를 쪼개서 돌리려면 index를 잘 가지고 놀아야 하는데 나는 도저히 잘 모르겠더라는,, ㅠ 구차해도 풀기만 하면 그만이다~~