[BOJ] 21609 ์ƒ์–ด ์ค‘ํ•™๊ต

๋ฌธ์ œ

๋ฌธ์ œ ์„ค๋ช…

Baekjoon Online Judge - 21609๋ฒˆ ์ƒ์–ด ์ค‘ํ•™๊ต

์ƒ์–ด ์ค‘ํ•™๊ต์˜ ์ฝ”๋”ฉ ๋™์•„๋ฆฌ์—์„œ ๊ฒŒ์ž„์„ ๋งŒ๋“ค์—ˆ๋‹ค. ์ด ๊ฒŒ์ž„์€ ํฌ๊ธฐ๊ฐ€ Nร—N์ธ ๊ฒฉ์ž์—์„œ ์ง„ํ–‰๋˜๊ณ , ์ดˆ๊ธฐ์— ๊ฒฉ์ž์˜ ๋ชจ๋“  ์นธ์—๋Š” ๋ธ”๋ก์ด ํ•˜๋‚˜์”ฉ ๋“ค์–ด์žˆ๊ณ , ๋ธ”๋ก์€ ๊ฒ€์€์ƒ‰ ๋ธ”๋ก, ๋ฌด์ง€๊ฐœ ๋ธ”๋ก, ์ผ๋ฐ˜ ๋ธ”๋ก์ด ์žˆ๋‹ค. ์ผ๋ฐ˜ ๋ธ”๋ก์€ M๊ฐ€์ง€ ์ƒ‰์ƒ์ด ์žˆ๊ณ , ์ƒ‰์€ M์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ ํ‘œํ˜„ํ•œ๋‹ค. ๊ฒ€์€์ƒ‰ ๋ธ”๋ก์€ -1, ๋ฌด์ง€๊ฐœ ๋ธ”๋ก์€ 0์œผ๋กœ ํ‘œํ˜„ํ•œ๋‹ค. (i, j)๋Š” ๊ฒฉ์ž์˜ i๋ฒˆ ํ–‰, j๋ฒˆ ์—ด์„ ์˜๋ฏธํ•˜๊ณ , |r1 - r2| + |c1 - c2| = 1์„ ๋งŒ์กฑํ•˜๋Š” ๋‘ ์นธ (r1, c1)๊ณผ (r2, c2)๋ฅผ ์ธ์ ‘ํ•œ ์นธ์ด๋ผ๊ณ  ํ•œ๋‹ค.

๋ธ”๋ก ๊ทธ๋ฃน์€ ์—ฐ๊ฒฐ๋œ ๋ธ”๋ก์˜ ์ง‘ํ•ฉ์ด๋‹ค. ๊ทธ๋ฃน์—๋Š” ์ผ๋ฐ˜ ๋ธ”๋ก์ด ์ ์–ด๋„ ํ•˜๋‚˜ ์žˆ์–ด์•ผ ํ•˜๋ฉฐ, ์ผ๋ฐ˜ ๋ธ”๋ก์˜ ์ƒ‰์€ ๋ชจ๋‘ ๊ฐ™์•„์•ผ ํ•œ๋‹ค. ๊ฒ€์€์ƒ‰ ๋ธ”๋ก์€ ํฌํ•จ๋˜๋ฉด ์•ˆ ๋˜๊ณ , ๋ฌด์ง€๊ฐœ ๋ธ”๋ก์€ ์–ผ๋งˆ๋‚˜ ๋“ค์–ด์žˆ๋“  ์ƒ๊ด€์—†๋‹ค. ๊ทธ๋ฃน์— ์†ํ•œ ๋ธ”๋ก์˜ ๊ฐœ์ˆ˜๋Š” 2๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์•„์•ผ ํ•˜๋ฉฐ, ์ž„์˜์˜ ํ•œ ๋ธ”๋ก์—์„œ ๊ทธ๋ฃน์— ์†ํ•œ ์ธ์ ‘ํ•œ ์นธ์œผ๋กœ ์ด๋™ํ•ด์„œ ๊ทธ๋ฃน์— ์†ํ•œ ๋‹ค๋ฅธ ๋ชจ๋“  ์นธ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•œ๋‹ค. ๋ธ”๋ก ๊ทธ๋ฃน์˜ ๊ธฐ์ค€ ๋ธ”๋ก์€ ๋ฌด์ง€๊ฐœ ๋ธ”๋ก์ด ์•„๋‹Œ ๋ธ”๋ก ์ค‘์—์„œ ํ–‰์˜ ๋ฒˆํ˜ธ๊ฐ€ ๊ฐ€์žฅ ์ž‘์€ ๋ธ”๋ก, ๊ทธ๋Ÿฌํ•œ ๋ธ”๋ก์ด ์—ฌ๋Ÿฌ๊ฐœ๋ฉด ์—ด์˜ ๋ฒˆํ˜ธ๊ฐ€ ๊ฐ€์žฅ ์ž‘์€ ๋ธ”๋ก์ด๋‹ค.

์˜ค๋Š˜์€ ์ด ๊ฒŒ์ž„์— ์˜คํ†  ํ”Œ๋ ˆ์ด ๊ธฐ๋Šฅ์„ ๋งŒ๋“œ๋ ค๊ณ  ํ•œ๋‹ค. ์˜คํ†  ํ”Œ๋ ˆ์ด๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ณผ์ •์ด ๋ธ”๋ก ๊ทธ๋ฃน์ด ์กด์žฌํ•˜๋Š” ๋™์•ˆ ๊ณ„์†ํ•ด์„œ ๋ฐ˜๋ณต๋˜์–ด์•ผ ํ•œ๋‹ค.

ํฌ๊ธฐ๊ฐ€ ๊ฐ€์žฅ ํฐ ๋ธ”๋ก ๊ทธ๋ฃน์„ ์ฐพ๋Š”๋‹ค. ๊ทธ๋Ÿฌํ•œ ๋ธ”๋ก ๊ทธ๋ฃน์ด ์—ฌ๋Ÿฌ ๊ฐœ๋ผ๋ฉด ํฌํ•จ๋œ ๋ฌด์ง€๊ฐœ ๋ธ”๋ก์˜ ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ๋ธ”๋ก ๊ทธ๋ฃน, ๊ทธ๋Ÿฌํ•œ ๋ธ”๋ก๋„ ์—ฌ๋Ÿฌ๊ฐœ๋ผ๋ฉด ๊ธฐ์ค€ ๋ธ”๋ก์˜ ํ–‰์ด ๊ฐ€์žฅ ํฐ ๊ฒƒ์„, ๊ทธ ๊ฒƒ๋„ ์—ฌ๋Ÿฌ๊ฐœ์ด๋ฉด ์—ด์ด ๊ฐ€์žฅ ํฐ ๊ฒƒ์„ ์ฐพ๋Š”๋‹ค. 1์—์„œ ์ฐพ์€ ๋ธ”๋ก ๊ทธ๋ฃน์˜ ๋ชจ๋“  ๋ธ”๋ก์„ ์ œ๊ฑฐํ•œ๋‹ค. ๋ธ”๋ก ๊ทธ๋ฃน์— ํฌํ•จ๋œ ๋ธ”๋ก์˜ ์ˆ˜๋ฅผ B๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, B2์ ์„ ํš๋“ํ•œ๋‹ค. ๊ฒฉ์ž์— ์ค‘๋ ฅ์ด ์ž‘์šฉํ•œ๋‹ค. ๊ฒฉ์ž๊ฐ€ 90๋„ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•œ๋‹ค. ๋‹ค์‹œ ๊ฒฉ์ž์— ์ค‘๋ ฅ์ด ์ž‘์šฉํ•œ๋‹ค. ๊ฒฉ์ž์— ์ค‘๋ ฅ์ด ์ž‘์šฉํ•˜๋ฉด ๊ฒ€์€์ƒ‰ ๋ธ”๋ก์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋ธ”๋ก์ด ํ–‰์˜ ๋ฒˆํ˜ธ๊ฐ€ ํฐ ์นธ์œผ๋กœ ์ด๋™ํ•œ๋‹ค. ์ด๋™์€ ๋‹ค๋ฅธ ๋ธ”๋ก์ด๋‚˜ ๊ฒฉ์ž์˜ ๊ฒฝ๊ณ„๋ฅผ ๋งŒ๋‚˜๊ธฐ ์ „๊นŒ์ง€ ๊ณ„์† ๋œ๋‹ค.

์˜คํ†  ํ”Œ๋ ˆ์ด๊ฐ€ ๋ชจ๋‘ ๋๋‚ฌ์„ ๋•Œ ํš๋“ํ•œ ์ ์ˆ˜์˜ ํ•ฉ์„ ๊ตฌํ•ด๋ณด์ž.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ๊ฒฉ์ž ํ•œ ๋ณ€์˜ ํฌ๊ธฐ N, ์ƒ‰์ƒ์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค.

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๊ฒฉ์ž์˜ ์นธ์— ๋“ค์–ด์žˆ๋Š” ๋ธ”๋ก์˜ ์ •๋ณด๊ฐ€ 1๋ฒˆ ํ–‰๋ถ€ํ„ฐ N๋ฒˆ ํ–‰๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ–‰์— ๋Œ€ํ•œ ์ •๋ณด๋Š” 1์—ด๋ถ€ํ„ฐ N์—ด๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ์นธ์˜ ์ •๋ณด๋Š” -1, 0, M์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ํš๋“ํ•œ ์ ์ˆ˜์˜ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค.

์ œํ•œ

  • 1 โ‰ค N โ‰ค 20
  • 1 โ‰ค M โ‰ค 5

ํ’€์ด

ํ•ด์„ค

1~5 ๋กœ์ง ์ˆœ์„œ๋Œ€๋กœ ๊ตฌํ˜„ํ•œ๋‹ค. ๋Œ€์‹  ๋‹ค์Œ์„ ์ฃผ์˜ํ•œ๋‹ค.

1)

  • N*N ๊ฐœ์˜ ์ขŒํ‘œ๋ฅผ ๋ชจ๋‘ ํ™•์ธํ•˜๋ฉด์„œ ์ผ๋ฐ˜ ๋ธ”๋ก์ด๊ณ  ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๊ฒฝ์šฐ dfs ํƒ์ƒ‰์„ ํ†ตํ•ด ์ธ์ ‘ํ•œ ๋ธ”๋ก ๊ทธ๋ฃน์„ ํƒ์ƒ‰ํ•œ๋‹ค.(0 ๋˜๋Š” ์ž๊ธฐ ์ž์‹ ์ธ ๋ธ”๋ก)
  • ์ด๋•Œ ๋ฌด์ง€๊ฐœ ๋ธ”๋ก(0)์€ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ํ•ด์ œํ•˜์—ฌ ๋‹ค๋ฅธ ๋ธ”๋ก ๊ทธ๋ฃน์—๋„ ํฌํ•จ๋  ์ˆ˜ ์žˆ๋„๋ก ํ•ด์•ผํ•œ๋‹ค.
  • 3)
  • ์ค‘๋ ฅ ๊ตฌํ˜„์€ ๊ฐ ์—ด๋งˆ๋‹ค ํ๋ฅผ ์ƒ์„ฑํ•˜์—ฌ ๋นˆ์นธ ์ขŒํ‘œ๋ฅผ ์ฐจ๊ณก์ฐจ๊ณก enqueueํ•˜๋„๋ก ํ•œ๋‹ค.
  • ๋‹จ, ๊ฒ€์€ ๋ธ”๋ก์„ ๋งŒ๋‚˜๋ฉด ํ๋ฅผ ์ดˆ๊ธฐํ™”ํ•ด์•ผํ•œ๋‹ค.

2์ฐจ์› ๋ฐฐ์—ด ์ขŒํ‘œ๋Š” 1์ฐจ์› ๋ฐฐ์—ด ์ขŒํ‘œ๋กœ ๋ณ€ํ™˜ํ•˜์—ฌ ๊ตฌํ˜„ํ–ˆ๋‹ค.

์‹œํ–‰์ฐฉ์˜ค

  • ํฌ๊ธฐ๊ฐ€ ๊ฐ€์žฅ ํฐ ๋ธ”๋ก ๊ทธ๋ฃน ๊ตฌํ•˜๋ฉด์„œ ์šฐ์„ ์ˆœ์œ„ ๊ตฌํ˜„์„ ์ž˜๋ชปํ•˜์—ฌ ํ…Œ์ผ€ 2๋ฒˆ์ด ๊ณ„์† ํ‹€๋ ธ๋‹ค.
  • ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๋ฐฉ๋ฌธ ํ•ด์ œ๋„ ๊ฒŒ์‹œํŒ ํ…Œ์ผ€๋ณด๊ณ  ๋’ค๋Šฆ๊ฒŒ ์•Œ์•„์ฑ˜๋‹ค..

์ฝ”๋“œ

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

/**
 * [1211] BOJ 21609 ์ƒ์–ด ์ค‘ํ•™๊ต
 * ๊ตฌํ˜„, 2์ฐจ์› ๋ฐฐ์—ด, ์™„์ „ํƒ์ƒ‰, dfs
 */

public class BOJ_21609_์ƒ์–ด์ค‘ํ•™๊ต {
	static final int VACANT = -2;       // ๋ธ”๋ก ์ œ๊ฑฐ ์ดํ›„ ๋นˆ ์นธ
	static final int BLACK = -1;        // ๊ฒ€์€ ๋ธ”๋ก
	static final int RAINBOW = 0;       // ๋ฌด์ง€๊ฐœ ๋ธ”๋ก
	
	static final int BLOCK_GROUP_SIZE = 0;       // maxBlockGroup ๋ฐฐ์—ด์˜ 0๋ฒˆ ์ธ๋ฑ์Šค(๊ทธ๋ฃน ๋‚ด ๋ธ”๋ก ๊ฐœ์ˆ˜)
	static final int RAINBOW_SIZE = 1;           // maxBlockGroup ๋ฐฐ์—ด์˜ 1๋ฒˆ ์ธ๋ฑ์Šค(๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๊ฐœ์ˆ˜)
	
	static int N, M, score, maxStandardBlock;    // ์ตœ๋Œ€ ๋ธ”๋ก ๊ทธ๋ฃน์˜ ๊ธฐ์ค€ ๋ธ”๋ก ์ขŒํ‘œ
	static int[] maxBlockGroup = new int[2];     // ๋ธ”๋ก ๊ทธ๋ฃน ์šฐ์„ ์ˆœ์œ„๋ฅผ ๋น„๊ตํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฐ์—ด(0: BLOCK_GROUP_SIZE, 1: RAINBOW_SIZE)
	static int[][] map, rotatedMap;
	static boolean[][] visited;
	static Map<Integer, List<Integer>> blockGroupMap = new HashMap<>();       // ๊ฐ ๋ธ”๋ก ๊ทธ๋ฃน์— ํฌํ•จ๋œ ๋ธ”๋ก ์ขŒํ‘œ๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ๋งต(key: ๊ธฐ์ค€ ๋ธ”๋Ÿญ ์ขŒํ‘œ, value: ๋ธ”๋ก ๊ทธ๋ฃน์— ํฌํ•จ๋œ ๋ธ”๋ก ์ขŒํ‘œ ๋ฆฌ์ŠคํŠธ)
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static Queue<Integer> rainbowPoints = new ArrayDeque<Integer>();          // ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๋ฐฉ๋ฌธ ํ•ด์ œํ•˜๊ธฐ ์œ„ํ•ด ๊ฐ dfs ํƒ์ƒ‰ ์‹œ ๋ฐฉ๋ฌธํ•œ ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ์ขŒํ‘œ ์ €์žฅ
	static Queue<Integer> vacantPoints = new ArrayDeque<Integer>();           // ์ค‘๋ ฅ ์ž‘์šฉ์„ ์œ„ํ•ด ์—ด ๋ณ„ ๋นˆ ์ขŒํ‘œ ์ €์žฅํ•˜๋Š” ํ

	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());
		
		visited = new boolean[N][N];
		map = new int[N][N];
		rotatedMap = 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());
		}
		
		// ์˜คํ†  ํ”Œ๋ ˆ์ด ์‹œ์ž‘
		while(findBlockGroups()) {      // ๋ธ”๋ก ๊ทธ๋ฃน ์กด์žฌํ•  ๋•Œ๊นŒ์ง€ ์˜คํ†  ํ”Œ๋ ˆ์ด ๋ฐ˜๋ณต
			removeAndGetScore();        // ๋ธ”๋ก ๊ทธ๋ฃน ์กด์žฌํ•˜๋ฉด ์ฐพ์€ ๊ทธ๋ฃน์„ ๋งต์—์„œ ์‚ญ์ œํ•˜๊ณ  ์ ์ˆ˜ ํš๋“
			actGravity();               // ์ค‘๋ ฅ ์ž‘์šฉ
			rotateMap();                // 90๋„ ๋ฐ˜์‹œ๊ณ„ ํšŒ์ „
			actGravity();               // ์ค‘๋ ฅ ์ž‘์šฉ
		}
		
		// ์ถœ๋ ฅ
		System.out.println(score);
	}

	// ๋ธ”๋ก ๊ทธ๋ฃน ์กด์žฌ ์—ฌ๋ถ€ ํŒŒ์•…
	private static boolean findBlockGroups() {
		// ์ดˆ๊ธฐํ™”
		for (boolean[] v : visited) Arrays.fill(v, false);    // ๋ฐฉ๋ฌธ ์ดˆ๊ธฐํ™”
		blockGroupMap.clear();                                // ๊ฐ ๋ธ”๋ก ๊ทธ๋ฃน ๋ณ„ ๋ธ”๋ก๋“ค ์ขŒํ‘œ ์ €์žฅํ•˜๋Š” ๋งต ์ดˆ๊ธฐํ™”
		Arrays.fill(maxBlockGroup, 0);                        // ๋ธ”๋ก ๊ทธ๋ฃน ๋ณ„ ํฌ๊ธฐ, ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๊ฐœ์ˆ˜ ๋ฐฐ์—ด ์ดˆ๊ธฐํ™”
		maxStandardBlock = -1;                                // ๊ฐ€์žฅ ํฐ ๋ธ”๋ก ๊ทธ๋ฃน์˜ ๊ธฐ์ค€ ๋ธ”๋ก ์ดˆ๊ธฐํ™”
		
		// N*N ๋ชจ๋“  ๊ฐ€๋Šฅํ•œ ์ขŒํ‘œ dfs ํƒ์ƒ‰
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (!visited[i][j] && map[i][j]>0) {          // ๋ฐฉ๋ฌธ ์•ˆํ–ˆ๊ณ  ์ผ๋ฐ˜ ๋ธ”๋ก์ธ ๊ฒฝ์šฐ๋งŒ ๊ธฐ์ค€ ์ขŒํ‘œ๋กœ ์‚ผ์•„ dfs
					rainbowPoints.clear();                    // ๋ฌด์ง€๊ฐœ ๋ธ”๋ก์€ ๋ฐฉ๋ฌธ์—ฌ๋ถ€ ์ดˆ๊ธฐํ™”ํ•ด์•ผํ•˜๋ฏ€๋กœ ํ์— ์ €์žฅํ•ด์•ผํ•จ. ์ด ํ๋ฅผ ์ดˆ๊ธฐํ™”
					
					int xy = i*N+j;                           // ๊ธฐ์ค€ ์ขŒํ‘œ
					int[] curblockGroup = findMaxBlockGroup(xy, i, j, map[i][j], new int[2]);      // dfs ํƒ์ƒ‰(๋ฐ˜ํ™˜ ๋ฐฐ์—ด : ๊ธฐ์ค€ ์ขŒํ‘œ ๋ธ”๋ก ๊ทธ๋ฃน์— ํฌํ•จ๋œ ๋ธ”๋ก ๊ฐœ์ˆ˜, ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๊ฐœ์ˆ˜ ์ €์žฅํ•œ ๋ฐฐ์—ด)
					if (curblockGroup[BLOCK_GROUP_SIZE]<2) continue;                               // ๋ธ”๋ก ๊ทธ๋ฃน์— ํฌํ•จ๋œ ๋ธ”๋ก ๊ฐœ์ˆ˜๊ฐ€ 2๊ฐœ ๋ฏธ๋งŒ์ด๋ฉด pass
					
					// ์šฐ์„ ์ˆœ์œ„ ๋น„๊ต(ํ–‰์—ด ์ขŒํ‘œ๊ฐ’์ด ์ž‘์€ ๊ฒฝ์šฐ๋จผ์ € ๋น„๊ตํ•˜๋ฏ€๋กœ ๋งŒ์•ฝ ๊ฐ’์ด ๊ฐ™์œผ๋ฉด ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ๋‚˜์ค‘์— ๋น„๊ตํ•˜๋Š” ์ขŒํ‘œ๋ฅผ ๊ธฐ์–ตํ•˜๋„๋ก ํ•จ
					if ((maxBlockGroup[BLOCK_GROUP_SIZE] < curblockGroup[BLOCK_GROUP_SIZE]) ||
						(maxBlockGroup[BLOCK_GROUP_SIZE] == curblockGroup[BLOCK_GROUP_SIZE] && maxBlockGroup[RAINBOW_SIZE] <= curblockGroup[RAINBOW_SIZE])) {
						// ์šฐ์„ ์ˆœ์œ„ ๋†’์€ ๋ธ”๋ก ๊ทธ๋ฃน์œผ๋กœ ๊ฐฑ์‹ 
						maxBlockGroup[BLOCK_GROUP_SIZE] = curblockGroup[BLOCK_GROUP_SIZE];
						maxBlockGroup[RAINBOW_SIZE] = curblockGroup[RAINBOW_SIZE];
						maxStandardBlock = xy;
					}
					
					clearRainbowVisit();                      // ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๋ฐฉ๋ฌธ์—ฌ๋ถ€ ์ดˆ๊ธฐํ™”
				}
			}
		}
		return (maxStandardBlock!=-1);                        // ๋ธ”๋ก ๊ทธ๋ฃน์ด ์กด์žฌํ•˜๋ฉด true ๋ฐ˜ํ™˜
	}

	// ๊ธฐ์ค€ ์ขŒํ‘œ ๋ณ„ ๋ธ”๋ก ๊ทธ๋ฃน ์ฐพ๊ธฐ(dfs)
	private static int[] findMaxBlockGroup(int xy, int x, int y, int color, int[] size) {
		visited[x][y] = true;       // ๋ฐฉ๋ฌธ ์ €์žฅ
		blockGroupMap.computeIfAbsent(xy, v -> new ArrayList<>()).add(x*N+y);    // ํ˜„์žฌ ๊ธฐ์ค€ ์ขŒํ‘œ์˜ ๋ธ”๋ก ๊ทธ๋ฃน ๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€
		size[BLOCK_GROUP_SIZE]++;   // ๋ธ”๋ก ๊ทธ๋ฃน ํฌ๊ธฐ ์ฆ๊ฐ€
		
		// 4๋ฐฉ ์ธ์ ‘ ํƒ์ƒ‰
		for (int i=0; i<4; i++) {
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			
			// ๊ฒฝ๊ณ„ ์•ˆ์ด๊ณ , ๋ฐฉ๋ฌธ ์•ˆํ–ˆ๊ณ , ์ž๊ธฐ ์ž์‹ ๊ณผ ๊ฐ™์€ ์ƒ‰์ƒ ํ˜น์€ ๋ฌด์ง€๊ฐœ ๋ธ”๋ก์ด๋ฉด ๋ธ”๋ก ๊ทธ๋ฃน์— ํฌํ•จ
			if (isInside(nx, ny) && !visited[nx][ny] && (map[nx][ny]==color || map[nx][ny]==RAINBOW)) {
				if (map[nx][ny]==RAINBOW) {      // ์ด๋•Œ ๋ฌด์žฌ๊ฐœ ๋ธ”๋ก์ด๋ฉด ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๊ฐœ์ˆ˜๋ฅผ ์ฆ๊ฐ€ํ•˜๊ณ  ๋‚˜์ค‘์— ๋ฐฉ๋ฌธ ํ•ด์ œํ•ด์ฃผ๊ธฐ ์œ„ํ•ด ํ์—๋„ ์ €์žฅ
					size[RAINBOW_SIZE]++;
					rainbowPoints.offer(nx);
					rainbowPoints.offer(ny);
				}
				findMaxBlockGroup(xy, nx, ny, color, size);      // ์žฌ๊ท€ ํƒœ์›Œ ๋ณด๋ƒ„(dfs)
			}
		}
		return size;      // ๋ธ”๋ก ๊ทธ๋ฃน ๋‚ด ๋ธ”๋ก ๊ฐœ์ˆ˜, ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•œ ๋ฐฐ์—ด ๋ฐ˜ํ™˜
	}
	
	// ๋ฌด์ง€๊ฐœ ๋ธ”๋ก ๋ฐฉ๋ฌธ ํ•ด์ œ
	private static void clearRainbowVisit() {
		while(!rainbowPoints.isEmpty()) {
			int x = rainbowPoints.poll();
			int y = rainbowPoints.poll();
			visited[x][y] = false;
		}
	}

	// ๋งต์—์„œ ๋ธ”๋ก ๊ทธ๋ฃน์„ ์ œ๊ฑฐํ•˜๊ณ  ์ ์ˆ˜ ํš๋“
	private static void removeAndGetScore() {
		for (int block : blockGroupMap.get(maxStandardBlock)) map[block/N][block%N] = VACANT;
		score += Math.pow(maxBlockGroup[BLOCK_GROUP_SIZE], 2);
	}
	
	// ์ค‘๋ ฅ ์ž‘์šฉ
	private static void actGravity() {
		for (int c=0; c<N; c++) {
			vacantPoints.clear();          // ๊ฐ ์—ด ๋ณ„ ๋นˆ ์ขŒํ‘œ ์ €์žฅํ•  ํ๋ฅผ ์ดˆ๊ธฐํ™”
			
			for (int r=N-1; r>=0; r--) {   // ์•„๋ž˜ ํ–‰๋ถ€ํ„ฐ ์œ„์˜ ํ–‰์œผ๋กœ ์˜ฌ๋ผ๊ฐ€๋ฉฐ
				int p = map[r][c];
				
				if (p==VACANT) {               // ๋นˆ ์ขŒํ‘œ๋ฉด ํ์— ์ €์žฅ
					vacantPoints.offer(r);
					vacantPoints.offer(c);
				} else if (p==BLACK) {         // ๋‹จ, ๊ฒ€์€ ๋ธ”๋ก์„ ๋งŒ๋‚˜๋ฉด ํ๋ฅผ ์ดˆ๊ธฐํ™”
					vacantPoints.clear();
				} else if (p>BLACK && !vacantPoints.isEmpty()) {    // ๊ฒ€์€์ƒ‰์ด ์•„๋‹Œ ๋ธ”๋ก์„ ๋งŒ๋‚ฌ๊ณ  ์•„๋ž˜์— ๋นˆ ์ขŒํ‘œ๊ฐ€ ์žˆ์œผ๋ฉด
					int x = vacantPoints.poll();                    // ํ์—์„œ ๋นˆ ์ขŒํ‘œ ๊บผ๋‚ด์„œ ํ•ด๋‹น ์ขŒํ‘œ์— ๋ธ”๋ก ์ €์žฅํ•˜๊ณ 
					int y = vacantPoints.poll();
					map[x][y] = p;
					map[r][c] = VACANT;
					vacantPoints.offer(r);                          // ๋ธ”๋ก์ด ์žˆ๋˜ ์ž๋ฆฌ๋Š” ๋‹ค์‹œ ๋นˆ์นธ์œผ๋กœ ๋งŒ๋“ค์–ด ํ์— ์ €์žฅ
					vacantPoints.offer(c);
				}
			}
		}
	}

	// ๋งต์„ 90๋„ ๋ฐ˜์‹œ๊ณ„ ํšŒ์ „
	private static void rotateMap() {
		for (int[] m : rotatedMap) Arrays.fill(m, 0);
		
		// 90๋„ ๋ฐ˜์‹œ๊ณ„ ํšŒ์ „ํ•˜์—ฌ ์ž„์‹œ ๋ฐฐ์—ด์— ์ €์žฅํ•˜๊ณ 
		for (int max=N-1, c=max; c>=0; c--) {
			for (int r=0; r<N; r++) rotatedMap[max-c][r] = map[r][c];
		}
		
		// ์ž„์‹œ ๋ฐฐ์—ด์„ ์›๋ณธ ๋ฐฐ์—ด์— ๋ณต์‚ฌํ•œ๋‹ค.
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) map[i][j] = rotatedMap[i][j];
		}
	}
	
	// ๊ฒฝ๊ณ„ ์ฒดํฌ
	public static boolean isInside(int nx, int ny) {
		return (nx>=0 && nx<N && ny>=0 && ny<N);
	}
}

๐Ÿ’ก

  • ๊นก์‹œ๋ฎฌโ€ฆ ์‚ด๋ ค์ฃผ์„ธ์š”โ€ฆ