백준 21609 상어 중학교 - 삼성 SW 역량 테스트 기출

백준 21609 상어 중학교 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

21609번: 상어 중학교

 

2. 문제 해결에 대한 아이디어

1. 기준 블록의 조건이 매우 많다.

      . 블록 그룹 중 무지개 블록이 아닌 블록 중

      . 행의 번호가 가장 작고

      . 열의 번호가 가장 작은 블록

2. 블록 그룹을 찾는 조건이 매우 많다.

      . 그룹의 크기는 2 이상이어야한다.

      . 크기가 가장 큰 블록 그룹을 찾는다.

      . 그 중 무지개 블록이 가장 많은 그룹을 찾는다.

      . 그 중에서 기준 블록의 행이 가장 큰 것을 찾는다.

      . 그 중에서 기준 블록의 열이 가장 큰 것을 찾는다.

3. 위 조건을 구현하기 위해, 블록 그룹을 ArrayList<Block>에 저장했다.

4. 블록 그룹에서 기준 블록을 쉽게 찾기 위해, compareTo를 구현하여 행과 sort하는데 사용했다.

5. 중력이 작용할 때, 빈 공간(-2)가 없을 때도 고려해줘야 한다. (구현 방법에 따라 다를 듯)

 

3. 코드

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;

public class Main {
	static class Block implements Comparable<Block> {
		int y, x;

		public Block(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		// 기준 블록을 찾기 위한 기준
		@Override
		public int compareTo(Block o) {
			if (this.y == o.y)
				return this.x - o.x;
			return this.y - o.y;
		}

	}

	static int N, M;
	static int[] dirY = { 1, -1, 0, 0 };
	static int[] dirX = { 0, 0, 1, -1 };
	static Block standard; //기준 블록
	static ArrayList<Block> group = new ArrayList<>();

	static int score = 0;
	static int[][] board;
	static boolean[][] visit;

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

		board = new int[N][N];
		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);
			}
		}

		while (true) {
			standard = new Block(-1, -1);
			group.clear();
			boolean stop = true;
			// step 1 : 삭제할 그룹 찾기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (board[i][j] > 0) {
						Block temp = new Block(i, j);
						if (selectGroup(temp) == 0) { //그룹이 없는 경우
							continue;
						}
						stop = false;
					}
				}
			}
			if (stop)
				break;
			
			// 2. 블록 그룹을 제거하고 블록의 수^2 만큼 점수 획득
			score += group.size() * group.size();
			for (int i = 0; i < group.size(); i++) {
				Block b = group.get(i);
				board[b.y][b.x] = -2; // 제거 표시
			}
			// 3. 중력 작용
			gravity();
			// 4. 반시계 회전
			rotate();
			// 5. 중력 작용
			gravity();

		}

		System.out.println(score);
	}

	static int selectGroup(Block target) {
		int color = board[target.y][target.x];
		Queue<Block> q = new LinkedList<>();
		ArrayList<Block> tempList = new ArrayList<>();
		visit = new boolean[N][N];
		visit[target.y][target.x] = true;
		q.add(target);

		while (!q.isEmpty()) {
			Block now = q.poll();
			tempList.add(now);

			for (int i = 0; i < 4; i++) {
				int yy = now.y + dirY[i];
				int xx = now.x + dirX[i];

				if (yy >= N || xx >= N || yy < 0 || xx < 0 || visit[yy][xx])
					continue;
				if (board[yy][xx] != 0 && board[yy][xx] != color) {
					continue;
				}

				q.add(new Block(yy, xx));
				visit[yy][xx] = true;
			}
		}

		if (tempList.size() < 2)
			return 0;

		boolean change = false;
		if (group.size() < tempList.size()) {
			change = true;
		} else if (group.size() == tempList.size()) {
			int cnt1 = 0, cnt2 = 0;
			for (int i = 0; i < group.size(); i++) {
				Block b = group.get(i);
				if (board[b.y][b.x] == 0) {
					cnt1++;
				}
			}
			for (int i = 0; i < tempList.size(); i++) {
				Block b = tempList.get(i);
				if (board[b.y][b.x] == 0) {
					cnt2++;
				}
			}
			if (cnt1 < cnt2) {
				change = true;
			} else if (cnt1 == cnt2) {
				Block standard1 = null, standard2 = null;
				Collections.sort(group);
				Collections.sort(tempList);
				for (int i = 0; i < group.size(); i++) {
					Block b = group.get(i);
					if (board[b.y][b.x] != 0) {
						standard1 = b;
						break;
					}
				}
				for (int i = 0; i < tempList.size(); i++) {
					Block b = tempList.get(i);
					if (board[b.y][b.x] != 0) {
						standard2 = b;
						break;
					}
				}
				if (standard1.y < standard2.y) {
					change = true;
				} else if (standard1.y == standard2.y) {
					if (standard1.x < standard2.x) {
						change = true;
					}
				}
			}
		}

		if (change) {
			group.clear();
			group.addAll(tempList);
			Collections.sort(group);
			for (int i = 0; i < group.size(); i++) {
				Block b = group.get(i);
				if (board[b.y][b.x] != 0) {
					standard.y = b.y;
					standard.x = b.x;
					break;
				}
			}
		}
		return tempList.size();
	}

	static void rotate() {
		int[][] copy = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				copy[N - 1 - j][i] = board[i][j];
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = copy[i][j];
			}
		}
	}

	static void gravity() {
		for (int i = N - 2; i >= 0; i--) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] >= 0) {
					int tempI = i + 1;
					while (tempI < N && board[tempI][j] == -2) {
						tempI++;
					}
					board[--tempI][j] = board[i][j];
					if (tempI != i)
						board[i][j] = -2;
				}
			}
		}
	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 자바를 써서 그런건지, 문제에 고려해야하는 조건이 많아진건지 200줄을 넘게 작성했다.

2. 기준 블록을 구하는 아이디어가 문제 풀이 시간을 단축해줬다.