백준 21609 상어중학교 (Gold2, SW)

전략

• 블록 표현 -1은 검정색, 0은 무지개, 일반블록 : 1~M

• 블록 그룹에는 최소 1개 이상의 일반 블록을 포함해야한다, 검은색 블록은 포함하면 안 되고 무지개 블록은 무한대로 포함가능, 블록의 기준 블록은 행이 가장 작고 열도 가장 작아야한다 -> BFS를 통해서 2차원 순회를 하면서 블록 그룹을 조건에 맞게 구해준다. 이때 무지개 블록은 다시 선택될 수 있도록 방문 처리를 지워줘야 한다

• 크기 가장 큰 블록을 선택하고 만약 같은게 있다면 무지개 블록이 많은 순 그 다음은 행이 큰 순, 열이 큰 순으로 선택한다. Comparator 써도 되는데 그냥 for 문으로 검사하는게 더 편해보인다

• 중력이 작용하면 일반 블록 + 무지개 블록은 검정 블록을 만나거나 경계를 만날 때 까지 떨어진다 움직일 블록 정하고 while 검정 블록이나 경계면을 만날 때까지 떨어트린다

• 반시계 회전하기 -> 인덱스를 통한 회전

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

class Node5 {
	int x;
	int y;
	int num;

	Node5(int x, int y, int num) {
		this.x = x;
		this.y = y;
		this.num = num;
	}
}

public class Main {
	static String[] in;
	static int N;
	static int M;
	static int[][] map;
	static boolean[][] visited;
	static Deque<Node5> dq;
	static ArrayList<Node5> RainbowList;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int cnt = 0;
	static int Bigx;
	static int Bigy;
	static int score;
	static int rainbowCnt;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		in = br.readLine().split(" ");
		N = Integer.parseInt(in[0]);
		M = Integer.parseInt(in[1]);
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			in = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(in[j]);
			}
		}

		while (true) {
			cnt = 0;
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!visited[i][j] && map[i][j] != -1 && map[i][j] != 0 && map[i][j] != -2) {
						pickBlock(i, j, map[i][j], false);
						//가장 큰 블록이 2가 안 되는 경우 
					}
				}
			}
			
			if(cnt<2) {
				System.out.println(score);
				System.exit(0);
			}
			
			//이 배열이 가장 큰 
			visited = new boolean[N][N];
			pickBlock(Bigx, Bigy, map[Bigx][Bigy], true);	
			
			score += cnt*cnt;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(visited[i][j] == true) {
						//빈칸으로 초기화
						map[i][j] = -2;
					}
				}
			}
			Gravity();
			Rotate();
			Gravity();	
		}
	}

	// BFS 탐색
	public static void pickBlock(int x, int y, int num, boolean check) {
		dq = new ArrayDeque<>();
		RainbowList = new ArrayList<>();
		Node5 nd = new Node5(x, y, num);
		dq.add(nd);
		visited[x][y] = true;
		int color = num;
		int numBlock = 1;
		int numRainbow = 0;

		while (!dq.isEmpty()) {
			Node5 nowNode = dq.poll();
			for (int i = 0; i < 4; i++) {
				int nx = nowNode.x + dx[i];
				int ny = nowNode.y + dy[i];

				if (nx < 0 || nx >= N || ny < 0 || ny >= N
						|| visited[nx][ny] | !(map[nx][ny] == 0 || map[nx][ny] == color))
					continue;
				Node5 newNode = new Node5(nx, ny, map[nx][ny]);
				dq.add(newNode);
				visited[nx][ny] = true;

				if (map[nx][ny] == 0) {
					RainbowList.add(newNode);
					numRainbow++;
				}
				numBlock++;
			}
		}

		if (check == false) {
			// 무지개 블록이면 다시 방문할 수 있도록 visited를 바꿔준다
			if (RainbowList.size() != 0) {
				for (int i = 0; i < RainbowList.size(); i++) {
					Node5 Rnode = RainbowList.get(i);
					visited[Rnode.x][Rnode.y] = false;
				}
			}
		}

		// 크기가 2보다 작은 그룹이라면 무효
		if (numBlock < 2)
			return;

		// 조건에 맞게 가장 큰 블록 설정하기
		if (numBlock == cnt) {
			//무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것
			if(rainbowCnt <= numRainbow) {
				Bigx = x;
				Bigy = y;
				cnt = numBlock;
				rainbowCnt = numRainbow;
			}
		}else if(numBlock>cnt) {
			Bigx = x;
			Bigy = y;
			cnt = numBlock;
			rainbowCnt = numRainbow;
		}

	}
	
	public static void Gravity() {
		for(int j = 0; j < N; j++) {
			for(int i = N-1; i >= 0; i--) {
				int x = i;
				int y = j;
				//검정색 블록이 아니라면
				if(map[x][y] != -1 && map[x][y]!=-2) {
					//범위를 벗어나지 않고 다음 이동할 블록칸이 비어있을 때 까지
					while((x+1)<N && map[x+1][y]== -2) {		
						int temp = map[x][y];
						map[x][y] = -2;
						map[x+1][y] = temp;
						x++;
					}
				}
			} 
		}
	}
	
	public static void Rotate() {
		
		int [][] temp = new int[N][N];
		
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<N; j++) {
				temp[N-j-1][i] = map[i][j];
			}
		}	
		map = temp;	
	}
}