21609_상어 중학교

사용 알고리즘: 구현빡!

사용 언어: java

 

오랜만에 빡구현 문제

중딩 상어 호온내주고 옴

 

package week12;

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

public class Main_bj_21609_상어중학교 {
	static int n,m, map[][], score;
	//아예 빈 칸은 -2로 표시
	
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	static boolean[][] turnVisit;

	public static void main(String[] args) {
		input_21609();
		
		//방문 배열을 2개 (턴별, dfs내에서 쓸 방문 배열)
		
		//게임 순서
		//1. 가장 큰 블록 그룹 찾기 +기준 블럭찾기+0의개수찾기 (최대 크기가 2이상이어야 함)
			//크기desc, 0의 개수desc, 기준행desc, 기준열desc
		//2. 블록 제거 후, 점수 합산(개수^2)
		//3. 중력 작용(-1) 제외
		//4. 반시계 방향으로 회전
		//5. 중력 작용(-1) 제외 => 1부터 반복
		while(true) {
			PriorityQueue<LinkedBlock> pq = new PriorityQueue<>((o1, o2) -> {
				if(o1.blocks.size() == o2.blocks.size()) {
					if(o1.jockerCnt == o2.jockerCnt) {
						if(o1.point[0] == o2.point[0]) {
							return o2.point[1] - o1.point[1];
						}
						return o2.point[0] - o1.point[0];
					}
					return o2.jockerCnt - o1.jockerCnt;
				}
				return o2.blocks.size() - o1.blocks.size();
			});
			
			//1.
			turnVisit = new boolean[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(map[i][j] >= 1 && !turnVisit[i][j]) { //일반 블럭이고, 방문 안 했을 때(블럭 그룹에 속하지 않았을 때) 그룹 만들기
						pq.add( blockGroup(i,j) );
					}
				}
			}
			
			if(pq.size()==0 || pq.peek().blocks.size() < 2) break; //오토 플레이 끝나는 조건
			
			//2.
			removeBlockAndScore(pq.peek());
			
			//3.
			gravity();
			
			//4.
			rotate();
			
			//5.
			gravity();
			
		}
		
		System.out.println(score);
	}

	private static void rotate() {
		//원래 i,j -> n-1 - j,i
		int[][] newMap = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				newMap[n-1-j][i] = map[i][j];
			}
		}
		
		map = newMap;
	}

	private static void gravity() { //-1은 움직이면 안 됨.
		for (int j = 0; j < n; j++) {
			Queue<Integer> row = new ArrayDeque<>();
			for (int i = n-1; i >= 0; i--) {
				if(map[i][j] == -2) row.add(i);
				else if(map[i][j] == -1) { //검은색 블럭
					row.clear();
				}
				else { //검은색 블럭 제외 나머지 블럭
					if(row.size() != 0) {
						int color = map[i][j];
						map[i][j] = -2;
						row.add(i);
						map[row.poll()][j] = color;
					}
				}
				
			}
		}
		
	}

	private static void removeBlockAndScore(LinkedBlock peek) {
		score += peek.blocks.size() * peek.blocks.size();
		
		for(int[] point : peek.blocks) {
			map[point[0]][point[1]] = -2;
		}
	}

	private static LinkedBlock blockGroup(int x, int y) {
		Queue<int[]> q = new ArrayDeque<>();
		boolean[][] visit = new boolean[n][n];
		
		int color = map[x][y];
		
		turnVisit[x][y] = true;
		visit[x][y] = true;
		
		q.add(new int[] {x, y});
		
		LinkedList<int[]> blocks = new LinkedList<>();
		int jockerCnt = 0;
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			blocks.add(new int[] {cur[0], cur[1]});
			if(map[cur[0]][cur[1]] == 0) jockerCnt++;
			
			for(int d=0; d<4; d++) {
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				
				if(nx>=0 && nx<n && ny>=0 && ny<n) {
					if(!visit[nx][ny] && (map[nx][ny] ==0 || map[nx][ny] ==color)) {
						q.add(new int[] {nx, ny});
						visit[nx][ny] = true;
						turnVisit[nx][ny] = true;
					}
				}
			}
		}
		
		return new LinkedBlock(blocks, new int[] {x,y}, jockerCnt);
	}

	private static void input_21609() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); //맵 크기
		m = sc.nextInt(); //색 개수
		
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
	}

}

class LinkedBlock {
	LinkedList<int[]> blocks; //블록 그룹의 블럭들(0포함)
	int[] point; //기준 블럭의 위치(0 제외한 정수)
	int jockerCnt; //블록 그룹 내 0의 개수
	
	public LinkedBlock(LinkedList<int[]> blocks, int[] point, int jockerCnt) {
		super();
		this.blocks = blocks;
		this.point = point;
		this.jockerCnt = jockerCnt;
	}
}

 

 

30%대에서 NPE가 발생했는데, -1로만 채워졌을 때를 고려해야 했다

-> if(pq.size()==0 || pq.peek().blocks.size() < 2) break; //오토 플레이 끝나는 조건

노란색으로 칠한 조건을 추가해줌.