[Java/자바 백준 21609] 상어 중학교

풀이

이틀정도 본 문제입니다. 테케가 다 돌아가는데 안돼서 뭘까 했는데

원인은 기준 블록이 가장 큰 행,열인 줄 알았는데, 기준 블록은 행, 열이 작은 것으로 잡아줘야합니다.

블록 크기가 가장 큰 그룹이 두개 이상이라면 기준 블록 중 무지개 블록이 많은 순, 행이 큰 순, 열이 큰 순으로 뽑아야합니다..

 

 

1번

bfs로 찾았습니다. comparable을 활용하여 블록 개수, 무지개 블록 갯수, 행, 열 순으로 정렬시켜주었습니다.

 

2번

같은 bfs를 구현하여 visited에 true로 표시하고 true인 값들을 모두 -2로 바꾸어주었습니다.

 

3번

gravity() 함수를 구현하였고 -1은 움직이지 않았습니다.

 

4번

삼성 문제는 회전시키기가 자주 나오는 것 같습니다.

https://velog.io/@domybest/2차원-배열-회전시키기

이 페이지를 참고해서 시계, 반시계에 대해서 규칙성을 찾았는데

외우면 편리할 거 같아서 외웠습니다.

 

5번

다시 gravity 활용했습니다.

import java.io.*;
import java.util.*;

public class Main{	
	static int N,M, answer;
	static int[][] map;
	static boolean[][] visited;
	static LinkedList<Block> list = new LinkedList<>();
	static Queue<int []> queue = new LinkedList<int[]>();
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	static private class Block implements Comparable<Block>{
		int totalPoint, rainbowPoint, row, col;
		public Block(int totalPoint, int rainbowPoint, int row, int col) {
			this.totalPoint = totalPoint;
			this.rainbowPoint = rainbowPoint;
			this.row = row;
			this.col = col;
		}
		
		public int compareTo(Block o) {
			if(this.totalPoint == o.totalPoint) {
				if(this.rainbowPoint == o.rainbowPoint) {
					if(this.row == o.row) {
						return o.col - this.col;
					}
					return o.row - this.row;
				}
				return o.rainbowPoint - this.rainbowPoint;
			}
			
			return o.totalPoint - this.totalPoint;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		visited = new boolean[N][N];
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0 ; j < N ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		while(true) {
			// 블록 그룹 찾기 2 이상 아니면 break;
			visited = new boolean[N][N];
			for(int i = 0 ; i < N ; i++) {
				for(int j = 0 ; j< N ; j++) {
					if(map[i][j] > 0 && visited[i][j] == false) {
						bfs(i, j, true);
					}
				}
			}
			if(list.isEmpty()) break;
			
			Collections.sort(list);
			// 찾은 블록 없애기
			visited = new boolean[N][N];
			bfs(list.get(0).row, list.get(0).col, false);
			removeBlock();

			// 중력
			gravity();
			// 반시계
			map = rotate();
			// 중력 
			gravity();
			
			list.clear();
		}
		System.out.println(answer);
	}

	private static int[][] 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];
			}
		}
		
		return temp;
	}

	private static void gravity() {
		for(int j = 0 ; j < N ; j++) {
			for(int i = N-1 ; i >= 0 ; i--) {
				for(int k = i ; k < N-1 ; k ++) {
					if(map[k][j] == -1) continue;
					if(map[k][j] != -2 && map[k+1][j] == -2) {
						int temp = map[k][j];
						map[k][j] = -2;
						map[k+1][j] = temp;
					}
				}
			}
		}
	}

	private static void removeBlock() {
		int count = 0;
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(visited[i][j] == true) {
					count++;
					map[i][j] = -2;
				}
			}
		}
		
		answer += (int)Math.pow(count, 2);
	}

	private static void bfs(int x, int y, boolean flag) {
		int blockPoint = map[x][y];
		visited[x][y] = true;
		queue.offer(new int[]{x, y});
		int totalPoint = 1;
		int rainbowPoint = 0;
		while(! queue.isEmpty()) {
			int cur[] = queue.poll();
			for(int i  = 0 ; i < 4 ; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				
				if(0 > nx || nx >= N || 0 > ny || ny >= N || visited[nx][ny] == true) continue;
				if(map[nx][ny] == blockPoint || map[nx][ny] == 0) {					
					if(map[nx][ny] == 0) rainbowPoint += 1;
					totalPoint += 1;
					visited[nx][ny] = true;
					queue.offer(new int[] {nx, ny});
				}
			}
		}
		
		if(totalPoint >= 2) list.add(new Block(totalPoint, rainbowPoint, x, y));
		if(flag == true) {
			for(int i = 0; i < N ; i++) {
				for(int j = 0 ; j < N ; j++) {
					if(map[i][j] == 0) visited[i][j] = false;
				}
			}
		}
		
	}
}