[BOJ] 21609 상어 중학교 (Java)

1. 문제 링크

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

21609번: 상어 중학교

 

2. 접근법

0. 변수 선언

PriorityQueue<Group> groups: 만들 수 있는 블록 그룹을 담아 우선순위에 따라 타겟 블록 그룹을 선정

 

1. 타겟 블록 그룹 찾기

1.1. searchMaxGroup() 함수를 통해 타겟 블록 그룹 반환하기

1.2. 그룹별 id 값을 매긴 후, 기준 블록을 찾아 bfs() 함수에 넘기기

1.3. bfs를 통해 블록의 수(cnt), 무지개 블록의 수(cntOfRainbow), 해당 블록 그룹에 담기는 블록들(tempBlocks)을 저장하며 탐색

1.4. 탐색 후, 방문했던 무지개 블록에 대해 visited[][] = false 처리 (다른 블록 그룹에서 무지개 블록은 재방문할 수 있음)

 

2. 블록 그룹이 존재하지 않는 경우(id를 -1 리턴함), 플레이 종료

 

3. deleteBlocks() 함수를 통해 타겟 블록 그룹에 포함된 블록들 제거하기

3.1. Group 클래스의 blocks에 저장둔 좌표값을 가지고 처리

3.2. blocks의 사이즈 제곱만큼 점수에 더하기

 

4. doGravity() 함수를 통해 격자에 중력 작용하기

4.1. 열 단위로 검은색 블록을 만나기 전까지의 블록을 찾고, 해당 블록부터 아래로 내려오며 빈칸과 버블 정렬하듯 자리 바꾸기

4.2. 타겟 블록(빈칸이 아닌 블록)과 타겟 블록 아래 칸(빈칸)의 자리를 바꾸기. 즉, 빈칸을 위로 올리기

 

5. rotateBoard() 함수를 통해 격자 회전하기

 

6. 다시 중력 작용하기

 

7. 1번으로 이동

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

// 상어 중학교

public class BJ21609 {

	private static class Group implements Comparable<Group>{
		int id;
		int cnt;
		int cntOfRainbow;
		int r;		// 기준 블록의 행
		int c;		// 기준 블록의 열
		ArrayList<Point> blocks = new ArrayList<>();

		Group(int id, int r, int c) {
			this.id = id;
			this.r = r;
			this.c = c;
		}

		@Override
		public int compareTo(Group o) {
			if(this.cnt == o.cnt) {
				if(this.cntOfRainbow == o.cntOfRainbow) {
					if(this.r == o.r) {
						return o.c - this.c;
					}
					return o.r - this.r;
				}
				return o.cntOfRainbow - this.cntOfRainbow;
			}
			return o.cnt - this.cnt;
		}
	}
	private static class Point {
		int x;
		int y;

		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int n, m;
	static int score;
	static int[][] board;		// 9인 경우, 제거된 블록
	static boolean[][] visited;
	static PriorityQueue<Group> groups = new PriorityQueue<>();		// 블록 그룹들을 담아 타겟 블록 그룹을 찾을 때 사용되는 큐
	static Queue<Point> queue = new LinkedList<>();					// bfs 탐색에 사용되는 큐
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};

	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());

		board = 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++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		solution();
		System.out.println(score);

	}
	
	private static void solution() {

		while(true) {

			// 타겟 블록 그룹을 찾음
			Group targetGroup = searchMaxGroup();
			// 블록 그룹이 존재하지 않는 경우, 플레이 종료
			if(targetGroup.id == -1) break;

			// 찾은 블록 그룹의 모든 블록을 제거
			deleteBlocks(targetGroup);

			// 격자에 중력이 작용
			doGravity();

			// 격자가 회전
			rotateBoard();

			// 격자에 중력이 작용
			doGravity();
			
			// 방문 여부 초기화
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					visited[i][j] = false;
				}
			}
		}
	}
	
	private static Group searchMaxGroup() {

		groups.clear();
		int id = 1;					// 블록 그룹에 매겨질 아이디
		boolean flag = false;		// 블록의 개수가 2 이상으로 이루어진 블록 그룹이 있는지의 여부

		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(visited[i][j] || board[i][j] == -1 || board[i][j] == 0 || board[i][j] == 9) continue;

				Group newGroup = bfs(id, i, j);		// 기준 블록(board[i][j])에서부터 id값으로 블록 그룹을 찾음
				if(newGroup.cnt > 1) {
					flag = true;
					groups.add(newGroup);
				}
				
				id++;
			}
		}
		
		if(groups.size() == 0 || !flag) return new Group(-1, -1, -1);		// 블록 그룹이 만들어지지 않거나, 블록의 개수가 2 이상으로 이루어진 블록 그룹이 없는 경우
		return groups.poll();
	}

	private static Group bfs(int id, int r, int c) {

		Group group = new Group(id, r, c);		// 리턴할 블록 그룹 선언
		int targetBlock = board[r][c];
		int cnt = 1;
		int cntOfRainbow = 0;
		ArrayList<Point> tempBlocks = new ArrayList<>();		// 해당 블록 그룹에 담길 블록들을 임시 저장

		visited[r][c] = true;
		queue.add(new Point(r, c));
		tempBlocks.add(new Point(r, c));

		while(!queue.isEmpty()) {
			Point poll = queue.poll();

			for(int i = 0; i < 4; i++) {
				int xx = poll.x + dx[i];
				int yy = poll.y + dy[i];

				if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
				if(visited[xx][yy]) continue;

				if(board[xx][yy] == targetBlock || board[xx][yy] == 0) {

					cnt++;
					if(board[xx][yy] == 0) cntOfRainbow++;
					visited[xx][yy] = true;
					queue.add(new Point(xx, yy));
					tempBlocks.add(new Point(xx, yy));
				}
			}
		}
		
		group.cnt = cnt;
		group.cntOfRainbow = cntOfRainbow;
		group.blocks = tempBlocks;

		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(board[i][j] == 0) visited[i][j] = false;		// 무지개 블록은 다른 블록 그룹에서 재방문할 수 있으므로 false로 변경
			}
		}

		return group;
	}

	private static void deleteBlocks(Group targetGroup) {

		for(Point block : targetGroup.blocks) {		// 타겟 블록 그룹의 블록들을 제거
			board[block.x][block.y] = 9;
		}

		score += targetGroup.blocks.size() * targetGroup.blocks.size();
	}

	private static void doGravity() {

		for(int j = 0; j < n; j++) {
			for(int i = n - 1; i >= 0; i--) {
				for(int k = i; k < n - 1; k++) {
					
					if(board[k][j] == -1) continue;
					if(board[k][j] != 9 && board[k + 1][j] == 9) {		// 빈칸과 일반 블록을 버블 정렬하듯 자리를 바꾸어 빈칸을 위로 올리기
						int temp = board[k][j];
						board[k][j] = board[k + 1][j];
						board[k + 1][j] = temp;
					}
				}
			}
		}
	}
	
	private static void rotateBoard() {
		
		int[][] temp = new int[n][n];
		
		for(int i = n - 1; i >= 0; i--) {
			for(int j = 0; j < n; j++) {
				temp[n - i - 1][j] = board[j][i];
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				board[i][j] = temp[i][j];
			}
		}
	}
	
}

 

4. 막힌 부분

(1) 중력 작용하기

구현 자체를 하는 게 어려웠다 ㅠ

배열을 만들어서 검정색 블록이 아닌 블록들을 담고 기준 index에 넣을까? 등등 고민했는데 현명하지 못한 방법 같았다.

결국 다른 분들 풀이 중 빈칸을 위로 올린다는 접근을 참고해서 풀었다.

 

(2) 무지개 블록은 여러 블록 그룹에 포함될 수 있다

라는 사실을 캐치하지 못했다.

문제에 명확하게 제시되지 않았는데 '틀렸습니다'를 마주한 후 질문 게시판 테케를 보고 깨달았다.

 

최근 푼 구현 문제 중 가장 해맸다.

집중적으로 구현 유형을 풀어오다 지난 주부터 면접이나 싸피 때문에 조금 느슨해졌는데

그래서 그런가..?ㅠ 꾸준히 하자.

 

5. 3개월 후 발전된 풀이

무지개 블록이 여러 블록 그룹에 포함될 수 있다는 걸 또 다시 놓친 바보 소영...

1시간만에 구현은 다 했는데 위 조건 때문에 30분을 더 썼다..

1시간 반 걸렸고, 풀이는 발전했다! (아주 조금 코드도 더 깔끔하고, 시간도 줄였다)

 

5.1. 바뀐 점

(1) 그룹별 속한 블록들을 ArrayList에 저장하지 않고, 삭제할 때 bfs 탐색을 한 번 더 돌렸다.

(2) 무지개 블록은 여러 블록에 속하기 때문에 방문처리를 신경써야 했는데,

     이전에는 이중 for문을 돌며 무지개 블록의 방문 값을 false로 처리해 주었다면, 이번에는 visited2[][] 배열을 두어서 (일반 + 무지개)와 (무지개) 방문처리 배열을 두 개 사용했다.

 

5.2. 코드

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

// 상어 중학교

public class BJ21609_2 {

	static class Group implements Comparable<Group> {
		int id;
		int x;
		int y;
		int cnt;
		int cntRB;
		
		Group(int id, int x, int y) {
			this.id = id;
			this.x = x;
			this.y = y;
		}
		
		@Override
		public int compareTo(Group o) {
			if(this.cnt == o.cnt) {
				if(this.cntRB == o.cntRB) {
					if(this.x == o.x) return o.y - this.y;
					return o.x - this.x;
				}
				return o.cntRB - this.cntRB;
			}
			return o.cnt - this.cnt;
		}
	}
	static int n, m;
	static int ans;
	static PriorityQueue<Group> groups = new PriorityQueue<>();
	static ArrayDeque<int[]> queue = new ArrayDeque<>();
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	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());
		
		int[][] map = new int[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());
			}
		}
		
		solution(map);
		System.out.println(ans);
	}
	
	private static void solution(int[][] map) {
		
		while(true) {
			if(makeGroups(map) == 0) break;
			deleteBlocks(map);
			doGravity(map);
			rotate(map);
			doGravity(map);
		}
	}
	
	private static int makeGroups(int[][] map) {
		
		groups.clear();
		boolean[][] visited = new boolean[n][n];		// makeGroups() 내 방문처리 배열 (무지개 블록 미포함)
		
		int idCnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(!visited[i][j] && 1 <= map[i][j] && map[i][j] <= m) bfs(++idCnt, i, j, map, visited);
			}
		}
		return groups.size();
	}
	
	private static void bfs(int id, int x, int y, int[][] map, boolean[][] visited) {
		
		boolean[][] visited2 = new boolean[n][n];		// bfs() 내 방문처리 배열 (무지개 블록 포함)
		Group newGroup = new Group(id, x, y);
		int cnt = 1;
		int cntRB = 0;
		visited[x][y] = true;
		visited2[x][y] = true;
		queue.add(new int[] {x, y});
		
		while(!queue.isEmpty()) {
			int[] xy = queue.poll();
			
			for(int d = 0; d < 4; d++) {
				int xx = xy[0] + dx[d];
				int yy = xy[1] + dy[d];
				if(xx < 0 || xx >= n || yy < 0 || yy >= n || visited2[xx][yy]) continue;
				
				if(map[xx][yy] == map[x][y] || map[xx][yy] == 0) {
					
					visited2[xx][yy] = true;									// 일반, 무지개 블록 모두 방문처리
					cnt++;
					queue.add(new int[] {xx, yy});
				
					if(map[xx][yy] == map[x][y]) visited[xx][yy] = true;		// 일반 블록만 방문처리
					else if(map[xx][yy] == 0) cntRB++;
				}
			}
		}
		
		if(cnt >= 2) {
			newGroup.cnt = cnt;
			newGroup.cntRB = cntRB;
			groups.add(newGroup);
		}
	}
	
	private static void deleteBlocks(int[][] map) {		// bfs 탐색을 통해 블록 제거하기
		
		Group group = groups.poll();
		ans += Math.pow(group.cnt, 2);
		int num = map[group.x][group.y];				// 타겟 번호
		
		map[group.x][group.y] = 9;						// 제거한 블록은 9로 표시
		queue.add(new int[] {group.x, group.y});
		
		while(!queue.isEmpty()) {
			int[] xy = queue.poll();
			
			for(int d = 0; d < 4; d++) {
				int xx = xy[0] + dx[d];
				int yy = xy[1] + dy[d];
				if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
				
				if(map[xx][yy] == num || map[xx][yy] == 0) {		// 타겟 번호이거나 무지개 블록인 경우
					map[xx][yy] = 9;
					queue.add(new int[] {xx, yy});
				}
			}
		}
	}
	
	private static void doGravity(int[][] map) {
		
		for(int j = 0; j < n; j++) {
			for(int i = n - 1; i > 0; i--) {
				if(map[i][j] == 9 && map[i - 1][j] != -1) {			// 아래가 빈 칸, 위가 검은색 블록이 아닌 경우라면
					
					int r = i;
					int c = j;
					while(true) {									// 계속해서 아래, 위를 교환하기
						int tmp = map[r][c];
						map[r][c] = map[r - 1][c];
						map[r - 1][c] = tmp;
						r++;
						if(r == n || map[r][c] != 9) break;			// 마지막 행이거나 빈 칸이 아니라면 교환 종료
					}
				}
			}
		}
	}
	
	private static void rotate(int[][] map) {
		
		int[][] tmp = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				tmp[j][i] = map[i][n - j - 1];
			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				map[i][j] = tmp[i][j];
			}
		}
	}
	
}