문제
https://www.acmicpc.net/problem/2933
입력
첫째 줄에 동굴의 크기 R과 C가 주어진다.
다음 R개 줄에는 C개의 문자가 주어진다.
다음 줄에는 막대를 던진 횟수 N이 주어진다.
마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다.
출력
입력 형식과 같은 형식으로 미네랄 모양을 출력한다.
풀이
제한조건
- (1 ≤ R,C ≤ 100)
- (1 ≤ N ≤ 100)
- '.'는 빈 칸, 'x'는 미네랄을 나타낸다.
- 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다.
- 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
- 공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.
- 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.
접근방법
시뮬레이션
시뮬레이션 문제는 문제의 주어진 조건을 차근차근 한 단계씩 해치우면 쉽다.
복잡해보여도 한 단계씩 진행해보자.
시뮬레이션이 아닌 실제 구현도 복잡할 수록 단계를 나누어 쉽더라.
1. 막대기 던지기.
2. 그룹 번호 부여하기.
3. 떨어질 그룹(클러스터) 아래로 떨어지게 하기.
4. 출력.1. 막대기 던지기.
두 사람이 번갈아가며 좌우에서 던진다는 사실만 주의하자.
크게 설명할 부분이 없다.
private static void throwBar(int h, int type) {
if (type == 0) {
// 좌 -> 우
for (int i = 0; i < C; ++i) {
if (map[R - h][i] == 'x') {
map[R - h][i] = '.';
break;
}
}
} else {
// 우 -> 좌
for (int i = C - 1; i >= 0; --i) {
if (map[R - h][i] == 'x') {
map[R - h][i] = '.';
break;
}
}
}
}2. 그룹 번호 부여하기.
위에서 막대기를 던진 부분의 크리스탈을 제거했다.
크리스탈이 제거됨으로 인하여, 클러스터가 나누어 졌을 수 있다.
나누어 졌다는 말은, 상하좌우 4방향으로 BFS를 수행했을 때, 서로 다른 그룹이 발생할 수 있다는 말이다.
여기서 주의
하나의 미네랄이 파괴되어서 떨어질 클러스터가 2개 이상 발생하지 않는다.
문제의 조건에서도 제시되었거니와, 생각을 해보면, 미네랄 파괴로 인하여 기존 1개가 2개로 분리되어도, 기존의 클러스터가 바닥에 붙어있으므로, 분리된 1쪽만 떨어지고 나머지 한쪽은 여전히 붙어있다. 친절하게 조건이 주어지지 않아도 생각할 수 있어야 함.
그룹을 구하는 이유는 분리된 특정 그룹 중 1개가 땅에서 떨어져서, 중력에 의해 바닥으로 떨어지기 때문이다.
그룹을 구하는 방식은 DFS, BFS 어떤것이든 상관없다.
3. 떨어질 그룹(클러스터) 아래로 떨어지게 하기.
위에서 몇개의 그룹이 있는지 찾았다.
그럼 바닥에서 떨어져있는 그룹이 어떤것인지 어떻게 찾을 수 있을까?
입력 예시 그룹 부여
****. 11110
...*. 00010
...*. 00010
**... -> 22000
**..* 22003
***.* 22203전체 입력을 순회하며, 찾는 방법이 있다.
(1번 그룹의 어떤 미네랄도 바닥 또는 다른 클러스터와 닿아 있지 않다.)
하지만, 막대가 던져질 때마다 전체 순회는 조금 비효율적이라 생각한다.
바닥과 인접한 그룹만 먼저 구해보자.
위의 예시와 같은 상황이라면 2와 3이 바닥과 닿아있다.
여기서 1을 찾기 위해서 여러 방법이 있지만, 수학적으로 계산해보자.
1부터 그룹의 번호를 부여했고, 최대 3까지 부여되었다면,
1~3까지의 누적합 (n*(n+1))/2 에서 인접한 그룹 번호(2,3)를 모두 뺀다면, 따로 떨어진 1개의 그룹번호1를 구할 수 있다.
이제 그룹 번호를 구했으니, 전체를 순회하며 더 내려갈 수 있는지 확인하며 한 칸씩 내려주자.
private static void fallDown(int maxGroupNum) {
int expect = (maxGroupNum * (maxGroupNum + 1)) / 2;
int sum = 0;
Set<Integer> s = new HashSet<>();
for (int i = 0; i < C; ++i)
s.add(visit[R - 1][i]);
sum = s.stream().mapToInt(Integer::intValue).sum();
// 모든 그룹이 바닥에 붙어있다.
if (sum == expect)
return;
int groupId = expect - sum;
while (true) {
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
if (visit[i][j] != groupId)
continue;
// 어딘가와 붙었다면 종료.
if (i + 1 == R || (visit[i + 1][j] != groupId && visit[i + 1][j] > 0))
return;
}
}
// 해당 그룹을 한 칸씩 모두 내린다.
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
if (visit[i][j] != groupId)
continue;
map[i + 1][j] = map[i][j];
map[i][j] = '.';
visit[i + 1][j] = visit[i][j];
visit[i][j] = 0;
}
}
}
}꼭 한 칸씩 내려야하나요? 라고 한다면 아니다. 계산을 통해 한 번에 내려도 된다.
하지만 미네랄이 하나 파괴되어 아래와 같은 구조가 된다면, 계산하는 과정이 충분히 복잡하므로 잘 생각하여 구현해야한다.
22222
00002
11102
10002
10002
10002
10222
10000
10000
10000
111114. 출력.
단순히 출력하면 된다.
Java의 경우 출력을 개선하기 위해 StringBuilder와 같은 객체를 사용하자.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
public class Main {
static int R, C, N;
static char[][] map;
static int[][] visit;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = in.readLine().split(" ");
R = stoi(inputs[0]);
C = stoi(inputs[1]);
map = new char[R][C];
for (int i = 0; i < R; ++i)
map[i] = in.readLine().toCharArray();
N = stoi(in.readLine());
inputs = in.readLine().split(" ");
for (int i = 0; i < N; ++i) {
visit = new int[R][C];
int h = stoi(inputs[i]);
throwBar(h, i % 2);
int maxGroupNum = assignGroup();
fallDown(maxGroupNum);
}
print();
}
private static int assignGroup() {
int count = 0;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (map[i][j] == 'x' && visit[i][j] == 0) {
count++;
visit[i][j] = count;
search(i, j);
}
}
}
return count;
}
private static void search(int startX, int startY) {
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {startX, startY});
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0];
int y = cur[1];
for (int d = 0; d < 4; ++d) {
int nextX = x + dx[d];
int nextY = y + dy[d];
if (isInRange(nextX, nextY) && map[nextX][nextY] == 'x' && visit[nextX][nextY] == 0) {
visit[nextX][nextY] = visit[x][y];
q.add(new int[] {nextX, nextY});
}
}
}
}
private static boolean isInRange(int x, int y) {
if (0 <= x && x < R && 0 <= y && y < C)
return true;
return false;
}
private static void fallDown(int maxGroupNum) {
int expect = (maxGroupNum * (maxGroupNum + 1)) / 2;
int sum = 0;
Set<Integer> s = new HashSet<>();
for (int i = 0; i < C; ++i)
s.add(visit[R - 1][i]);
sum = s.stream().mapToInt(Integer::intValue).sum();
// 모든 그룹이 바닥에 붙어있다.
if (sum == expect)
return;
int groupId = expect - sum;
while (true) {
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
if (visit[i][j] != groupId)
continue;
// 어딘가와 붙었다면 종료.
if (i + 1 == R || (visit[i + 1][j] != groupId && visit[i + 1][j] > 0))
return;
}
}
// 해당 그룹을 한 칸씩 모두 내린다.
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
if (visit[i][j] != groupId)
continue;
map[i + 1][j] = map[i][j];
map[i][j] = '.';
visit[i + 1][j] = visit[i][j];
visit[i][j] = 0;
}
}
}
}
private static void print() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
sb.append(map[i][j]);
}
sb.append("\n");
}
System.out.println(sb);
}
private static void throwBar(int h, int type) {
if (type == 0) {
// 좌 -> 우
for (int i = 0; i < C; ++i) {
if (map[R - h][i] == 'x') {
map[R - h][i] = '.';
break;
}
}
} else {
// 우 -> 좌
for (int i = C - 1; i >= 0; --i) {
if (map[R - h][i] == 'x') {
map[R - h][i] = '.';
break;
}
}
}
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}