이해
격자판에 미네랄이 존재합니다.
미네랄은 클러스터 단위로 구분할 수 있습니다. 이 때의 클러스터는 서로 인접한 미네랄의 집합입니다. 다시 말해, 떨어진 미네랄 집합끼리는 별개의 클러스터라고 할 수 있습니다.
주어진 격자판에 대해 입력만큼 막대기를 던집니다. 막대기와 미네랄이 부딪히면 미네랄은 제거됩니다. 단, 막대기를 던지는 위치는 왼쪽부터 시작해 오른쪽과 번갈아 바뀝니다.
막대기에 의해 미네랄이 부서진다면 기존의 클러스터가 분리될 수 있습니다. 분리된 클러스터가 만일 공중에 떠있는 상태라면 중력에 의해서 바닥에 떨어지게 됩니다. 클러스터가 다른 클러스터나 바닥을 만나기 전까진 계속 떨어집니다. 다른 클러스터와 만난다면 서로 합쳐지게 됩니다.
N번의 막대기를 던지고 최종적으로 남게된 격자판의 상태를 출력하면 됩니다.
접근
과정은 크게 2가지로 나눌 수 있습니다.
1. 막대기를 던진다. (미네랄이 부서진다.)
2. 격자판의 상태를 갱신한다. (중력에 의해 클러스터가 떨어진다.)
1번의 과정은 2번에 영향을 미치지 않으며 단순히 격자판에서 미네랄을 제거할 뿐입니다. 좌우를 번갈아 가면서 막대기를 던지고 진행 방향에 미네랄이 있다면 없애주기만 하면 되는 단순한 과정입니다.
2번의 경우, 새롭게 격자판의 상태를 어떻게 갱신할 것인가에 대해서 고민이 생길 수 있습니다. 문제에 조건에 나와있듯이 최초에 입력으로 주어진 클러스터는 공중에 떠오를 수 없습니다. 또한 막대기에 의해 2개 이상의 클러스터가 동시에 떨어지는 경우도 존재하지 않습니다. 그렇다면 막대기를 던질 때 새로운 클러스터가 생기거나 생기지 않는다는 두 가지 경우밖에 존재하지 않습니다.
그렇다면 막대기를 던질 때마다 새로운 클러스터를 찾아야 합니다. 찾는 방식에 대해서 생각해봅시다. 클러스터는 서로 인접한 미네랄의 집합이기 때문에 BFS로 그 집합들을 구분할 수 있습니다. Flood Fill 알고리즘과 유사합니다.
특정 클러스터가 공중에 떠있는 지 확인하려면 모든 미네랄 구역을 조사해야 합니다. 바닥에 닿지 않는 클러스터를 발견하면 이 정보를 저장하고 다음 과정으로 넘어갑니다.
새 클러스터는 중력에 의해 아래로 떨어져야 합니다. 그 과정은 어렵지 않습니다. 이전 과정에서 새 클러스터의 구역을 BFS로 모두 탐색했기 때문에 모든 미네랄 구역의 정보를 가지고 있습니다. 해당 좌표를 모두 순회하여 중력이 적용될 거리만큼 당기면 되겠습니다.
그렇다면 중력이 적용될 거리는 어떻게 될까요? 문제에 힌트가 있습니다. 클러스터의 모든 열을 조사하여 몇 칸 떨어질 수 있는지 구할 수 있습니다. 좌표를 모두 가지고 있기 때문에 모두 탐색하면 되겠습니다.
풀이
while (!q.isEmpty()) {
xy cur = q.poll();
for (int k = 0; k < 4; k++) {
int nx = cur.x + d[0][k];
int ny = cur.y + d[1][k];
if (IsOutBound(nx, ny) || board[nx][ny] != 'x' || visited[nx][ny]) {
continue;
}
if (nx == N - 1) {
isFloat = false;
}
q.add(new xy(nx, ny));
visited[nx][ny] = true;
target.add(new xy(nx, ny));
}
}위 코드는 분리된 클러스터를 찾는 FloodFill 알고리즘에서 BFS를 수행하는 코드입니다. 일반적인 BFS와 동일하지만 nx가 N-1이면 즉, 땅과 접해있다면 isFloat를 false로 초기화합니다.
target은 클러스터의 좌표 리스트로 매 BFS를 수행할 때마다 clear를 합니다. 만일, 조사한 클러스터가 분리된 클러스터라면 해당 리스트의 정보를 clear하지 않고 그대로 가지고 나옵니다.
private static void DownCluster(int n) {
int down = N;
for (int i = 0; i < M; i++) {
int maxColPos = -1;
int bottom = N;
for (int j = 0; j < N; j++) {
if (board[j][i] == 'M') {
maxColPos = Math.max(maxColPos, j);
}
}
for (int j = maxColPos + 1; j < N; j++) {
if (board[j][i] == 'x') {
bottom = j;
break;
}
}
// 해당 열에 클러스터가 없다면
if (maxColPos == -1) {
continue;
}
// 있다면
down = Math.min(down, bottom - maxColPos - 1);
}
// down만큼 모두 하강하면됨
for (xy cdnt : target) {
board[cdnt.x][cdnt.y] = '.';
}
for (xy cdnt : target) {
board[cdnt.x + down][cdnt.y] = 'x';
}
} 중력을 적용하는 DownCluster 메소드입니다. 문제의 힌트대로 클러스터의 모든 열을 조사합니다. 이전에 클러스터를 조사하는 과정에서 분리된 클러스터의 미네랄은 'M'으로 표현했습니다. (전체 코드 참고)
이를 통해 특정 열의 클러스터의 경계값을 확인하고 아래서부터 바닥에 위치한 클러스터의 높이를 확인합니다.
이 둘의 차이만큼 클러스터를 하강시키면 되겠습니다. target은 이전 과정에서 가져온 분리된 클러스터의 좌표 리스트입니다.
코드
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class prob2933 {
static class xy {
int x;
int y;
public xy(int x, int y) {
this.x = x;
this.y = y;
}
}
static final int[][] d = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
static int N, M, K;
static List<xy> target = new ArrayList<>();
static char[][] board;
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());
board = new char[101][101];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = s.charAt(j);
}
}
K = Integer.parseInt(br.readLine());
String s[] = br.readLine().split(" ");
for (int i = 0; i < K; i++) {
int h = Integer.parseInt(s[i]);
// 막대 던지기
ThrowStick(i, h);
// BFS로 공중에 떠있는 미네랄 찾기
FloodFill(i);
// 미네랄 내리기 (떠있는 미네랄은 i로 표시함)
if (target.size() > 0) {
DownCluster(i);
}
}
PrintBoard();
}
private static void DownCluster(int n) {
int down = N;
for (int i = 0; i < M; i++) {
int maxColPos = -1;
int bottom = N;
for (int j = 0; j < N; j++) {
if (board[j][i] == 'M') {
maxColPos = Math.max(maxColPos, j);
}
}
for (int j = maxColPos + 1; j < N; j++) {
if (board[j][i] == 'x') {
bottom = j;
break;
}
}
// 해당 열에 클러스터가 없다면
if (maxColPos == -1) {
continue;
}
// 있다면
down = Math.min(down, bottom - maxColPos - 1);
}
// down만큼 모두 하강하면됨
for (xy cdnt : target) {
board[cdnt.x][cdnt.y] = '.';
}
for (xy cdnt : target) {
board[cdnt.x + down][cdnt.y] = 'x';
}
}
private static void FloodFill(int n) {
boolean[][] visited = new boolean[101][101];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] != 'x' || visited[i][j]) {
continue;
}
boolean isFloat = true;
// bfs
target.clear();
Queue<xy> q = new ArrayDeque<>();
q.add(new xy(i, j));
target.add(new xy(i, j));
visited[i][j] = true;
while (!q.isEmpty()) {
xy cur = q.poll();
for (int k = 0; k < 4; k++) {
int nx = cur.x + d[0][k];
int ny = cur.y + d[1][k];
if (IsOutBound(nx, ny) || board[nx][ny] != 'x' || visited[nx][ny]) {
continue;
}
if (nx == N - 1) {
isFloat = false;
}
q.add(new xy(nx, ny));
visited[nx][ny] = true;
target.add(new xy(nx, ny));
}
}
// bfs가 끝남
// 조사한 클러스터가 떠있으면
// list에 저장된 좌표를 "M"로 치환
if (isFloat) {
target.forEach(o -> board[o.x][o.y] = 'M');
return;
}
}
}
target.clear();
}
private static boolean IsOutBound(int nx, int ny) {
return nx < 0 || nx >= N || ny < 0 || ny >= M;
}
private static void ThrowStick(int i, int h) {
if (N - h < 0 || N - h >= N) {
return;
}
if (i % 2 == 0) {
for (int col = 0; col < M; col++) {
if (board[N - h][col] == 'x') {
board[N - h][col] = '.';
return;
}
}
} else {
for (int col = M - 1; col >= 0; col--) {
if (board[N - h][col] == 'x') {
board[N - h][col] = '.';
return;
}
}
}
}
private static void PrintBoard() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sb.append(board[i][j]);
// if (board[i][j] == 'x') {
// sb.append(board[i][j]);
// } else {
// sb.append('.');
// }
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}