백준 21609 : 상어 중학교

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

21609번: 상어 중학교

[ 문제풀이 ]

2021년 상반기 오전 삼성 공채 SW 역량 테스트 문제 중 하나인 상어 중학교 문제이다. 시험 당시 문제 자체는 어렵지 않았는데 문제를 꼼꼼하게 읽지 않아서 빼먹는 조건이 많아서 시간이 많이 소요됐던 문제이다.

​시험 당시 블록 그룹의 기준 블록을 선택하는 조건과 중력에 의해 블록을 떨어뜨리는 작업을 잘못 이해해서 애를 먹었는데 문제를 꼼꼼히 읽는다면 특별한 알고리즘은 요구되지 않기 때문에 어렵지 않게 해결할 수 있을 것이다.

​빈 공간을 표현하기 위해 -2로 선언하였고 무지개 블록과 일반 블록의 중복 방문을 구별하기 위해 visit 배열을 일반 블록의 수만큼 선언하여 탐색하도록 하였다.

​다행히도 이 문제도 당시 풀었던 풀이로 AC를 받았다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Node implements Comparable<Node> {
		int y, x, cnt, rainBowCnt;

		public Node(int y, int x, int cnt, int rainBowCnt) {
			this.y = y;
			this.x = x;
			this.cnt = cnt;
			this.rainBowCnt = rainBowCnt;
		}

		@Override
		public int compareTo(Node o) {
			if (this.cnt == o.cnt) {
				if (this.rainBowCnt == o.rainBowCnt) {
					if (this.y == o.y) {
						return o.x - this.x;
					}
					return o.y - this.y;
				}
				return o.rainBowCnt - this.rainBowCnt;
			}
			return o.cnt - this.cnt;
		}
	}
	
	static int N, M, sby, sbx, blockCnt, rainBowCnt, answer;
	static int[][] map, temp;
	static boolean[][][] visit;
	static List<Node> list;
	static Queue<Integer> q;
	
	static int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));) 
		{
			map = new int[21][21];
			temp = new int[21][21];
			visit = new boolean[6][21][21];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			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());
				}
			}
			
			list = new ArrayList<>();
			q = new LinkedList<>();
			
			while (true) {
				for (int i = 0; i < N; ++i) {
					for (int j = 0; j < N; ++j) {
						//일반 블록이 아니라면
						if (map[i][j] <= 0 || visit[map[i][j]][i][j]) continue;
						
						sby = i; sbx = j;
						blockCnt = 0; rainBowCnt = 0;
						dfs(i, j, map[i][j]);
						
						if (blockCnt + rainBowCnt >= 2) {
							list.add(new Node(sby, sbx, blockCnt, rainBowCnt));
						}
					}
				}
				
				//블록 그룹이 존재하지 않는다면 종료
				if (list.isEmpty()) break;
				
				Collections.sort(list);
				
				Node node = list.get(0);
				answer += node.cnt * node.cnt;
				list.clear();
				
				remove(node);
				down();
				rotate();
				down();
				init();
			}
			bw.write(answer + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void init() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 1; k <= M; ++k) {
					visit[k][i][j] = false;
				}
			}
		}
	}

	//무지개 블록과 v 블록으로 그룹을 만듬
	public static void dfs(int y, int x, int v) {
		blockCnt++;
		visit[v][y][x] = true;
		
		if (map[y][x] == 0) {
			rainBowCnt++;
		} else {
			//기준 블록 갱신
			if (y <= sby) {
				if (y < sby) {
					sby = y;
					sbx = x;
				} else {
					if (x < sbx) {
						sby = y;
						sbx = x;
					}
				}
			}
		}
		
		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];
		
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (map[ny][nx] <= -1 || visit[v][ny][nx]) continue;
			if (map[ny][nx] == 0 || map[ny][nx] == v) {
				dfs(ny, nx, v);
			}
		}
	}

	//1에서 찾은 블록 그룹의 모든 블록을 제거
	public static void remove(Node node) {
		int v = map[node.y][node.x];
		
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				visit[v][i][j] = false;
			}
		}
		
		dfs(node.y, node.x, v);
		
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (visit[v][i][j]) {
					map[i][j] = -2;
				}
			}
		}
	}

	//블록에 중력 적용
	//검은 블록을 만나면 즉시 종료되는 것이 아니라
	//검은 블록 위에서 다시 중력이 적용됨
	public static void down() {
		for (int j = 0; j < N; ++j) {
			int y = N - 1;
			for (int i = N - 1; i >= 0; --i) {
				if (map[i][j] == -1) {
					while (!q.isEmpty()) {
						map[y--][j] = q.poll();
					}
					while (y > i) {
						map[y--][j] = -2;
					}
					y--;
				} else {
					if (map[i][j] != -2) {
						q.offer(map[i][j]);
					}
				}
			}
			
			while (!q.isEmpty()) {
				map[y--][j] = q.poll();
			}
			while (y >= 0) {
				map[y--][j] = -2;
			}
		}
	}
	
	//반시계 방향 회전
	public static void rotate() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				temp[N - j - 1][i] = map[i][j];
			}
		}
		
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				map[i][j] = temp[i][j];
			}
		}
	}
}