[백준] 18500. 미네랄 2
문제 링크
풀이 과정
파괴된 미네랄로 인해 클러스터가 분리되면, 새로 파생된 클러스터가 공중에 떠 있을 수가 있습니다. 이 때, 공중에 떠있는 이 클러스터를 모양의 변화 없이 아래로 내려야 합니다. 모양을 유지하기 위해선 한 칸씩 내릴 수 있기에, 클러스터에 속한 모든 미네랄의 좌표를 알아야 할 필요가 있습니다. 또한, 파괴된 미네랄의 좌표가 아래 사진과 같을 때, 파괴된 미네랄의 아래 부분 역시 공중에 뜰 수 있기에 파괴된 미네랄의 상, 하, 좌, 우 를 모두 확인해 봐야 했습니다.
알고리즘은 다음과 같습니다.
- 해당 높이에 막대를 던지면 제일 처음 만나는 미네랄을 파괴합니다.
- 미네랄이 파괴되어 새로운 클러스터가 생성되면, 그 클러스터를 밑으로 내려야하는 지 확인합니다.
- 새로 생성된 클러스터가 공중에 떠 있게 되어 바닥으로 내려가야 된다면, 바닥에 맞닿을 때까지 한 칸씩 밑으로 내립니다.
- 위 과정을 반복합니다.
Point target = null;
if (n % 2 == 0) {
for (int j = 0; j < C; j++) {
if (map[i][j] == '.') continue;
map[i][j] = '.';
target = new Point(i, j);
break;
}
} else {
for (int j = C - 1; j >= 0; j--) {
if (map[i][j] == '.') continue;
map[i][j] = '.';
target = new Point(i, j);
break;
}
}
if (target == null) continue;
미네랄을 파괴하는 코드는 위와 같습니다. 막대가 날아가는 경로에 미네랄이 존재한다면, 미네랄을 파괴시킨 다음 빈 칸으로 둡니다. 또한 파괴된 좌표의 값을 변수 target 에 저장합니다.
Queue<Point> queue = new LinkedList<>();
for (int i = 0; i < R; i++)
Arrays.fill(visit[i], false);
queue.add(next);
visit[next.x][next.y] = true;
cluster.add(next);
while (!queue.isEmpty()) {
Point now = queue.poll();
if (now.x == R - 1) {
cluster.clear();
break;
}
for (int dd = 0; dd < 4; dd++) {
int ni = now.x + di[dd];
int nj = now.y + dj[dd];
if (!check(ni, nj) || visit[ni][nj] || map[ni][nj] == '.') continue;
visit[ni][nj] = true;
queue.add(new Point(ni, nj));
cluster.add(new Point(ni, nj));
}
}
findCluster 메소드는 미네랄 파괴로 인해 분리된 클러스터가 있는 지 확인합니다. 상, 하, 좌, 우 방향으로 bfs 탐색을 실행하며, 클러스터로 묶여 있는 미네랄들의 좌표를 cluster 리스트에 담습니다.
if (now.x == R - 1) {
cluster.clear();
break;
}
이 때, 클러스터를 이루는 어느 미네랄의 좌표의 행이 R-1 에 해당하면, 이는 클러스터가 바닥에 닿아있음을 의미하므로, 공중에 떠있지 않은 클러스터임을 확인할 수 있습니다. 해당 클러스터는 공중에 떠 있지 않으므로(바닥으로부터 연결되므로), 클러스터를 내리는 과정을 생략합니다.
if (p.x == R - 1 || (p.x + 1 <= R - 1 && map[p.x + 1][p.y] == 'x' && !cluster.contains(new Point(p.x + 1, p.y)))) {
bottom = true;
}
down 메소드는 클러스터를 바닥으로 내리는 작업을 실행합니다. 현재 좌표가 바닥이거나, 한 칸을 내렸을 때 그 좌표가 다른 클러스터에 속해 있다면 내리는 작업을 그만합니다.
코드
import java.awt.*;
import java.util.*;
import java.util.List;
public class Main {
static int R, C, N;
static char[][] map;
static boolean[][] visit;
static List<Point> cluster;
static int[] di = {-1, 1, 0, 0};
static int[] dj = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
map = new char[R][C];
visit = new boolean[R][C];
cluster = new ArrayList<>();
for (int i = 0; i < R; i++) {
map[i] = sc.next().toCharArray();
}
N = sc.nextInt();
for (int n = 0; n < N; n++) {
int height = sc.nextInt();
int i = R - height;
Point target = null;
if (n % 2 == 0) {
for (int j = 0; j < C; j++) {
if (map[i][j] == '.') continue;
map[i][j] = '.';
target = new Point(i, j);
break;
}
} else {
for (int j = C - 1; j >= 0; j--) {
if (map[i][j] == '.') continue;
map[i][j] = '.';
target = new Point(i, j);
break;
}
}
if (target == null) continue;
findCluster(target);
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
static void findCluster(Point target) {
for (int d = 0; d < 4; d++) {
cluster.clear();
Point next = new Point(target.x + di[d], target.y + dj[d]);
if (!check(next.x, next.y)) continue;
if (map[next.x][next.y] == 'x') {
Queue<Point> queue = new LinkedList<>();
for (int i = 0; i < R; i++)
Arrays.fill(visit[i], false);
queue.add(next);
visit[next.x][next.y] = true;
cluster.add(next);
while (!queue.isEmpty()) {
Point now = queue.poll();
if (now.x == R - 1) {
cluster.clear();
break;
}
for (int dd = 0; dd < 4; dd++) {
int ni = now.x + di[dd];
int nj = now.y + dj[dd];
if (!check(ni, nj) || visit[ni][nj] || map[ni][nj] == '.') continue;
visit[ni][nj] = true;
queue.add(new Point(ni, nj));
cluster.add(new Point(ni, nj));
}
}
if (!cluster.isEmpty())
down();
}
}
}
static void down() {
while (true) {
boolean bottom = false;
for (Point p : cluster) {
if (p.x == R - 1 || (p.x + 1 <= R - 1 && map[p.x + 1][p.y] == 'x' && !cluster.contains(new Point(p.x + 1, p.y)))) {
bottom = true;
}
}
if (bottom) break;
for (Point p : cluster) {
map[p.x][p.y] = '.';
}
for (Point p : cluster) {
map[p.x + 1][p.y] = 'x';
p.x++;
}
}
}
static boolean check(int i, int j) {
if (i < 0 || i > R - 1 || j < 0 || j > C - 1) return false;
return true;
}
}
댓글남기기