BOJ - 상어 중학교 21609번 (JAVA)

❓ 문제 - 백준 상어 중학교 21609번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/21609)

21609번: 상어 중학교

 

 

📝 문제해결법

1. 이 문제는 구현+BFS으로 풀었다.

• Block 객체로 한 블록 그룹의 정보를 저장한다. x, y는 기준 블록의 위치, size는 블록의 사이즈, mu_cnt는 무지개 블록의 갯수이다. 
• 2차원 배열 0행 0열부터 쭉 접근하면서 BFS를 통해 최대 길이의 블록 그룹을 찾는다. 만약 찾은 블록들이 그룹의 크기가 2이상이면 블록 그룹 list에 블록 정보를 넣는다. visited 배열은 블록 그룹이 연결된 것들의 무지개 블록을 제외한 것의 방문처리를 하는 것이고 visited2는 bfs 내에서 방문처리를 위해 사용하는 배열이다.
• 무지개 블록은 다른 색깔이 다른 블록 그룹에 포함될 수 있기 때문에 visited 배열에서는 방문처리를 안 해줘야 한다.
• 그리고 블록 그룹 중에서 길이가 가장 큰, 그리고 길이가 같다면 무지개 블록의 갯수가 많은, 그리고 무지개 블록 개수가 많다면, 기준 블록의 행이 큰, 행이 같다면 열이 큰 순으로 정렬한다. 그리고 해당 기준으로 뽑힌 하나의 블록 그룹이 존재하지 않는다면 while을 빠져나오고, 블록 그룹이 존재한다면 해당 블록 그룹을 제거 처리 해줘야 한다.
• 블록 그룹을 제거 처리하기 위해 기준 블록에 대한 정보를 바탕으로 bfs2() 메소드로 제거 처리를 진행해준다. 제거된 블록은 -2로 표기한다.
• 블록 그룹이 제거되었다면 중력처리를 위해 맨 밑 행부터 밑으로 끌어 당기는 작업을 수행한다. 만약 현재 보는 행이 비어있는 상태(-2)라면 위에 자기 자신으로 끌어당길 블록들을 위로 올라가면서 찾고 검은 블록이 아닌 다른 블록을 찾는다면 현재 행으로 위치 시켜주고 끌어당기는 위치 부분은 비어줌처리(-2) 해준다.
• 그리고 moving 함수를 통해 90도 반시계 방향으로 전환한다.

 

 

💻 소스코드

// BOJ - 상어 중학교 (21609번)
// BFS + 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.concurrent.LinkedBlockingDeque;

public class Main_21609 {
	public static int n, m;
	public static int[][] map;
	public static boolean[][] visited;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static class Block implements Comparable<Block>{
		int x;
		int y;
		int size;
		int mu_cnt;
		public Block(int x, int y, int size, int mu_cnt) {
			this.x = x;
			this.y = y;
			this.size = size;
			this.mu_cnt = mu_cnt;
		}
		@Override
		public int compareTo(Block o) {
			if(this.size == o.size) {
				if(this.mu_cnt == o.mu_cnt) {
					if(this.x == o.x) {
						return -(this.y - o.y);
					}
					return -(this.x - o.x);
				}
				return -(this.mu_cnt-o.mu_cnt);
			}
			return -(this.size - o.size);
		}
	}
	public static ArrayList<Block> list;
	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());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		visited = new boolean[n][n];
		list = new ArrayList<>();
		
		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());
			}
		}
		
		int score = 0;
		
		while(true) {
			// 최대 길이 블록 그룹 찾기
			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] > 0) {
						bfs(i, j, map[i][j]);
					}
				}
			}
			
			Collections.sort(list);
			// 블록 그룹 제거
			if(list.size() == 0) {
				break;
			}
			
			
			Block b = list.get(0);
		
			bfs2(b.x, b.y);
			score += b.size * b.size;
			
			
			// 중력
			fall();
			
			// 반시계 회전
			moving();
			
			// 중력
			fall();
		
			list.clear();
		}
		
		
		

		
		System.out.println(score);
	}
	
	public static void print() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				System.out.print(map[i][j] +" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public static void moving() {
		int[][] temp = new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				temp[i][j] = map[j][n-i-1];
			}
		}
		map = temp;
	}
	
	public static void fall() {
		for(int j=0;j<n;j++) {
			for(int i=n-1;i>=1;i--) {
				if(map[i][j] != -2) continue;
				int nx = i;
				while(true) {
					nx -= 1;
					if(nx < 0) break;
					if(map[nx][j] == -1) break;
					if(map[nx][j] != -2) {
						map[i][j] = map[nx][j];
						map[nx][j] = -2;
						break;
					}
				}
			}
		}
	}
	
	public static void bfs2(int x, int y) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {x, y});
		int c = map[x][y];
		map[x][y] = -2;
		while(!q.isEmpty()) {
			int[] arr = q.poll();
			for(int d=0;d<4;d++) {
				int nx = arr[0] + dx[d];
				int ny = arr[1] + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(map[nx][ny] == 0 || map[nx][ny] == c) {
						map[nx][ny] = -2;
						q.add(new int[] {nx, ny});
					}
				}
			}
		}
		
	}
	
	public static void bfs(int x, int y, int c) {
		boolean[][] visited2 = new boolean[n][n];
		
		visited[x][y] = true;
		visited2[x][y] = true;
		Queue<int[]> q = new LinkedList<>();
		int size = 1;
		int mu_cnt = 0;
		q.add(new int[] {x, y});
		
		while(!q.isEmpty()) {
			int[] arr = q.poll();
			for(int d=0;d<4;d++) {
				int nx = arr[0] + dx[d];
				int ny = arr[1] + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(map[nx][ny] == -1) continue;
					
					if(!visited2[nx][ny]) {
						if(map[nx][ny] == 0) {
							mu_cnt++;
							size++;
							visited2[nx][ny] = true;
							q.add(new int[] {nx, ny});
						} else if(map[nx][ny] == c) {
							size++;
							visited[nx][ny] = true;
							visited2[nx][ny] = true;
							q.add(new int[] {nx, ny});
							
						}
					}
				}
			}
		}
		
		if(size == 1) {
			return;
		} else {
			list.add(new Block(x, y, size, mu_cnt));
		}
		
	}

}