[PS] 백준 2933 - 미네랄

* 문제 링크

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

2933번: 미네랄

문제 이해

1. 주어지는 입력은 동굴의 상태로써 기존에 많이 풀었던 문제와 달리 테트리스 같은 높이가 있는 문제이다.

2. "각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다 " 문제의 이 내용이 처음에 이해가 잘 안 갔었는데 결국에는 한 칸이 미네랄이고 칸이 붙어있으면은 클러스터라는 뜻이다.

3. 두 사람이 번갈아가며 막대기를 던지면서 미네랄이 있는 칸을 만나면 칸이 비워지고 그때 어떤 클러스터가 공중에 떠있다면 떨어진다.

 

문제 풀이

주어지는 동굴의 R과 C가 100 이하이고 막대기를 던지는 횟수가 100 이하이기 때문에 백만 정도로 동굴을 몇번 탐색한다 하더라도 1초는 안 걸릴 것으로 예상된다.

크게 해야 될 작업은 공중에 떠있는 클러스터를 체크하는 일과 바닥으로 떨어지는 클러스터를 처리하는 일이다.

 

*어려웠던 부분

클러스터를 부수고 나서 공중에 떠있는 클러스터를 떨어트릴 때 바닥이나 바닥에 붙어있는 클러스터와 닿으면 멈추게 해야 하기 때문에 깊은 복사로 맵을 하나 더 만들어서 바닥에 붙은 클러스터를 표시해주었다.

떨어지는 부분도 한 칸씩 움직여주게 되면 최대 100만큼 움직일 수 있기에 계산이 1억이 돼버려서 시간 초과가 날 우려가 있어 한번에 옮겨주는 부분을 구현하는데도 시간이 걸렸다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_2933_G3_미네랄 {

	public static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	public static int R, C;
	public static char[][] tmpMap, Map;

	public static boolean isIn(int r, int c) {
		return r >= 0 && c >= 0 && r < R && c < C;
	}

	public static char[][] deepCopy(char[][] original) {
		char[][] ret = new char[original.length][original[0].length];
		for (int i = 0; i < ret.length; i++) {
			System.arraycopy(original[i], 0, ret[i], 0, original[0].length);
		}
		return ret;
	}

	public static int checkCluster() {
		// 클러스터가 있는지 확인
		int ret = 0;
		tmpMap = deepCopy(Map);
		boolean[][] visited = new boolean[R][C];
		for (int c = 0; c < C; c++) {
			// 맨 밑에꺼만 확인하면 됨
			if (Map[R - 1][c] == 'x' && !visited[R - 1][c]) { // 안떨어지는 cluster
				ret++;
				Queue<int[]> q = new LinkedList<>();
				int[] start = { R - 1, c };
				q.add(start);
				visited[R - 1][c] = true;
				tmpMap[R - 1][c] = 'C'; // 바닥에 붙은 클러스터 표시
				while (!q.isEmpty()) {
					int[] node = q.poll();
					for (int d = 0; d < dir.length; d++) {
						int nr = node[0] + dir[d][0];
						int nc = node[1] + dir[d][1];
						if (isIn(nr, nc) && Map[nr][nc] == 'x' && !visited[nr][nc]) {
							visited[nr][nc] = true;
							tmpMap[nr][nc] = 'C';
							int[] temp = { nr, nc };
							q.add(temp);
							ret++;
						}
					}
				}
			}
		}
		return ret;
	}

	public static void gravity() {
		int min = Integer.MAX_VALUE;

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (tmpMap[r][c] == 'x') {
					int h = 0;
					for (int nr = r + 1; nr < R; nr++) { // 바로 밑부터 땅까지
						if (tmpMap[nr][c] == 'C') { // 다른 클러스터
							break;
						} else if (tmpMap[nr][c] == 'x') {
							h = min;
							break;
						} else {
							h++;
						}
					}
					min = Math.min(min, h);
				}
			}
		}
		// 이제 최소 높이만큼만 이동
		for (int r = R - 2; r >= 0; r--) {
			for (int c = 0; c < C; c++) {
				if (tmpMap[r][c] == 'x') {
					Map[r][c] = '.';
					Map[r + min][c] = 'x';
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = 0;
		R = sc.nextInt();
		C = sc.nextInt();
		Map = new char[R][C];
		for (int r = 0; r < R; r++) {
			Map[r] = sc.next().toCharArray();
			for (int c = 0; c < C; c++) {
				if (Map[r][c] == 'x') {
					count++;
				}
			}
		}
		int N = sc.nextInt();

		boolean turn = true;
		for (int i = 0; i < N; i++) {
			int h = sc.nextInt();
			if (turn) {// true 왼쪽
				for (int c = 0; c < C; c++) {
					if (Map[R - h][c] == 'x') {
						Map[R - h][c] = '.';
						count--;
						break;
					}
				}
			} else {
				for (int c = C - 1; c >= 0; c--) {
					if (Map[R - h][c] == 'x') {
						Map[R - h][c] = '.';
						count--;
						break;
					}
				}
			}
			//막대기를 던져서 미네랄이 부셔졌다면
			if (count != checkCluster()) {
				gravity();
			}
			turn = !turn;
		}
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				System.out.print(Map[r][c]);
			}
			System.out.println();
		}
	}

}