[백준] 21609 - 상어 중학교 (Java)

[백준] 21609 - 상어 중학교 (Java)

문제

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

풀이/후기

내가 처음 풀었던 풀이는 visited에 블록 그룹 번호를 부여해서

해당 그룹이 가장 크면 그룹 번호를 이용해 삭제하는 로직을 이용했다.

근데 이렇게 하니 무지개 블록 처리가 애매해졌다.

list를 이용해서 가장 큰 블록 그룹에서 사용한 무지개 블록을 담아두고

추후에 삭제하는 방향으로 수정도 해보았는데 계속 오답처리가 되더라.

이 방법으로 꼭 완성해보고 싶었는데 결국 방향을 바꿨다.

 

visited는 boolean으로 둔다

매 블록 그룹을 찾기 전에 무지개 블록의 visited는 다시 false로 돌려준다.

이 경우 나중에 블록을 제거할 때의 방법이 고민이었는데

그냥 BFS를 한 번 더 태우면 된다.

 

그 이후에는 각자 기능을 하는 함수들을 잘 적어서 실행해주면 많이 어렵지는 않다.

회전하는 함수는 이전에 해봐서 다행히 바로 구현할 수 있었다.

중력 함수는 좀 고민이 필요했는데

회전, 중력 모두 삼성에서 자주 출제하는 유형이라고 하니 확실히 숙지해야겠다.

 

또한 계속해서 class를 이용하는 것을 외면하고 있었는데

역시 사용하니까 편하다.

새로운 유형의 풀이에 거부감 느끼지 말고

제때제때 습득해서 활용할 생각을 하자.

 

 

하 정말 이 문제 때문에 하루종일 고통받았다,,,

어제 저녁 스터디 시간에 풀기 시작한 문제를 오늘 7시 반이 다 되어서야 성공하다니,,^^

정말 풀릴듯 풀리지 않아 더 답답했다.

하나하나의 잔실수 때문에 더 그랬던 것 같은데

정말 이렇게 긴 코드는 어디서부터 어떻게 검토할지도 막막해 엄청난 집중력이 필요한 것 같다.

 

코드

package Samsung;

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

public class Problem21609 {

	static int N, M;
	static int[][] map;
	static boolean[][] vis;
	static int score = 0;

	static Queue<int[]> q = new LinkedList<>();
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(str.nextToken());
		M = Integer.parseInt(str.nextToken());

		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			str = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(str.nextToken());
			}
		}

		while (true) {

			// 가장 큰 블록 그룹 찾기
			Block resBlock = findBlockFunc();

			// 더이상 블록 그룹이 존재하지 않으면 종료
			if (resBlock == null) {
				break;
			}

			// 점수 계산
			score += resBlock.sum * resBlock.sum;

			// 블록 그룹 제거
			removeFunc(resBlock);

			// 중력 작용
			gravityFunc();

			// 회전
			rotateFunc();

			// 중력 작용
			gravityFunc();

		}

		System.out.println(score);

	}

	// 크기가 가장 큰 블록 그룹 찾는 함수
	static Block findBlockFunc() {
		vis = new boolean[N][N];
		Block maxBlock = new Block(0, 0, 0, Integer.MIN_VALUE, Integer.MIN_VALUE);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {

				// 검정 블록이면 SKIP
				if (map[i][j] == -1) {
					continue;
				}

				// 빈칸이면 SKIP
				if (map[i][j] == -2) {
					continue;
				}

				// 무지개 블록이면 SKIP
				if (map[i][j] == 0) {
					continue;
				}
				if (vis[i][j]) {
					continue;
				}

				// 블록 그룹 탐색 전에 무지개 블록 방문 처리 초기화
				initRainbowFunc();

				// 블록 그룹 탐색 BFS
				// color의 번호, 기준 색상의 위치 (i,j)를 들고 이동
				Block cur = bfsFunc(i, j, map[i][j]);

				// 블록 그룹의 크기가 2보다 작으면 SKIP
				if (cur == null) {
					continue;
				}

				// 가장 큰 블록 그룹 찾기
				if (maxBlock.compareBlock(cur)) {
					maxBlock = cur;
				}
			}
		}

		// 블록 그룹을 찾지 못한 경우 NULL 리턴
		if (maxBlock.color == 0) {
			return null;
		}

		return maxBlock;

	}

	// 무지개 블록 방문 처리 초기화 함수
	static void initRainbowFunc() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0) {
					vis[i][j] = false;
				}
			}
		}
	}

	static Block bfsFunc(int x, int y, int color) {
		q.add(new int[] { x, y });
		vis[x][y] = true;
		int sum = 1; // 블록 그룹의 크기
		int rs = 0; // 블록 그룹에 포함된 무지개 블록의 개수

		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cx = cur[0];
			int cy = cur[1];

			for (int i = 0; i < 4; i++) {
				int nx = cx + dir[i][0];
				int ny = cy + dir[i][1];

				if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
					continue;
				}

				if (map[nx][ny] == -1) {
					continue;
				}

				if (map[nx][ny] == -2) {
					continue;
				}

				if (vis[nx][ny]) {
					continue;
				}

				// color가 다를 때 무지개 블록이면 블록 그룹에 추가
				if (map[nx][ny] != color) {
					if (map[nx][ny] == 0) {
						rs++;
						sum++;
						vis[nx][ny] = true;
						q.add(new int[] { nx, ny });
					}
					continue;
				}

				// 위 조건에 모두 포함되지 않으면
				sum++;
				vis[nx][ny] = true;
				q.add(new int[] { nx, ny });

			}

		}

		if (sum < 2) {
			return null;
		} else {
			return new Block(x, y, color, sum, rs);
		}

	}

	// 블록 그룹을 제거하는 함수
	static void removeFunc(Block block) {
		vis = new boolean[N][N];
		vis[block.x][block.y] = true;
		map[block.x][block.y] = -2;
		q.add(new int[] { block.x, block.y });

		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cx = cur[0];
			int cy = cur[1];

			for (int i = 0; i < 4; i++) {
				int nx = cx + dir[i][0];
				int ny = cy + dir[i][1];

				if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
					continue;
				}

				if (map[nx][ny] == -1) {
					continue;
				}

				if (map[nx][ny] == -2) {
					continue;
				}

				if (vis[nx][ny]) {
					continue;
				}

				// color가 다른 것 중에 무지개인 경우 제거
				if (map[nx][ny] != block.color) {
					if (map[nx][ny] == 0) {
						q.add(new int[] { nx, ny });
						vis[nx][ny] = true;
						map[nx][ny] = -2;
					}
					continue;
				}

				// 위 조건에 모두 포함되지 않으면
				// 블록그룹 제거 (-2)
				q.add(new int[] { nx, ny });
				vis[nx][ny] = true;
				map[nx][ny] = -2;
			}
		}
	}

	// 중력 작용 함수
	static void gravityFunc() {
		for (int i = 0; i < N; ++i) {
			// 가장 아래에서(N-1) 바로 윗 칸(N-1)에서 시작
			for (int j = N - 2; j >= 0; --j) {
				if (map[j][i] == -1) {
					continue;
				}
				if (map[j][i] == -2) {
					continue;
				}

				int dest = j + 1;
				while (true) {
					if (dest == N)
						break;
					if (map[dest][i] == -2)
						dest++;
					else
						break;
				}
				if (dest == j + 1)
					continue;
				map[dest - 1][i] = map[j][i];
				map[j][i] = -2;
			}
		}
	}

	// 90도 회전 함수
	static void rotateFunc() {
		int[][] temp = new int[N][N];

		int x = 0;
		int y = 0;
		for (int j = N - 1; j >= 0; j--, x++) {
			y = 0;
			for (int i = 0; i < N; i++, y++) {
				temp[x][y] = map[i][j];
			}
		}

		map = temp;
	}

	static class Block {
		int x, y, color, sum, rs;

		public Block(int x, int y, int color, int sum, int rs) {
			this.x = x;
			this.y = y;
			this.color = color;
			this.sum = sum;
			this.rs = rs;
		}

		// 블록 그룹 비교 함수
		public boolean compareBlock(Block other) {
			// other가 더 크면 TRUE

			if (this.sum != other.sum) {
				return this.sum < other.sum;
			}

			if (this.rs != other.rs) {
				return this.rs < other.rs;
			}

			if (this.x != other.x) {
				return this.x < other.x;
			}

			return this.y < other.y;
		}
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/44d1aaff2d32a69b1e9cc3eab06d5b89ac2f595a

참고

이 풀이가 정말정말 도움이 많이 되었다.

풀이 자체가 너무 깔끔하고 주석 설명도 잘 되어 있었다.

한참 고민 많이하고 고통 받을 때 가이드처럼 도움이 되었다.

나도 이렇게 깔끔한 풀이를 할 수 있는 사람이 되어야지!

https://gogigood.tistory.com/71