문제 정보
2933번: 미네랄
창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄
www.acmicpc.net
문제 파악
문제 조건
1 ≤ R,C ≤ 100 / 1 ≤ N ≤ 100 / 1 <= 막대의 높이 <= R
공중에 떠있는 미네랄 클러스터는 없으며, 두 개 이상의 클러스터가 동시에 떨어지는 경우도 없음
문제 내용
문제를 이해하는 데에 시간이 많이 소요되었던 문제이다.
이 문제는 그림으로 설명하는 것이 가장 빠를 것 같으니, 그림으로 설명해보도록 하겠다
먼저, '.' 과 'x' 로 이루어진 칸 들이 있다. 이들은 R행 C열만큼 즉, R*C개 존재한다.
두 칸이 상하좌우에 인접해 있다면, 그 둘은 같은 클러스터 라고 한다.
노란 형광펜으로 이어진 집합이 클러스터 이다. 이들은 어떠한 칸에서라도 다른 칸까지 상하좌우 인접한 칸들을 통해 연결되어 있음을 알 수 있다.
창영과 상근 두 사람은 각각 왼쪽, 오른쪽에서 순서대로 막대기를 던진다.
왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽 -> .....
막대기를 던질 때에는 높이가 주어지며, 던지는 방향에서 맞는 첫번째 미네랄은 파괴된다.
만약 높이 4에서 첫번째로 막대를 던졌다면, 분홍색 형광펜이 있는 위치의 미네랄 하나가 파괴되는 것이다.
만약 해당 미네랄이 파괴된다면, 해당 미네랄을 기준으로 위에 있는(높이 5에 있는 두개의 미네랄) 클러스터와 아래로 연결된 6개의 미네랄의 클러스터는 분리된다. 또한 분리된 클러스터는 아래로 떨어진다.(추락한다는 표현이 맞을 듯)
두개의 칸을 가진 클러스터가 아래로 떨어져서 after 과 같은 결과가 만들어졌다.
해당 클러스터가 아래로 떨어지는 동안, 어떠한 다른 클러스터와 충돌하지 않았기 때문에 바닥으로 떨어졌다.
다음과 같은 경우도 발생할 수 있다
만약 떨어지는 동안에 아래에 다른 클러스터의 일부분이 존재하는 경우에는, 그곳에서 멈추게 된다
위에 설명했던 점들을 고려하여, 막대를 여러번 던지고 난 후의 미네랄 모양을 구하는 문제이다.
풀이
생각했던 내용
처음에는, union_find 를 사용해서 각 위치에서의 부모(root)를 찾고 root가 다를 시 다른 클러스터라고 판단하여 작업을 하면 되겠구나 했지만, 해당 부분에 대한 이해가 깊지 않아서 2차원 배열에서 union_find 를 어떤식으로 작성해야 하는지 쉽게 판단할 수 없었다.
풀이한 내용
클러스터가 분리되었음을 알 수 있는 방법은 여러가지가 있을 수 있지만, 나는 위에서 설명했듯 클러스터가 분리되어 떨어질 때에는 다른 클러스터의 위에 떨어지거나, 바닥에 떨어져야 한다는 사실에 집중했다.
만약 다른 클러스터 위에 떨어졌다면 해당 클러스터와 합쳐졌을 것이고, 바닥에 떨어졌다면 클러스터의 일부분이 바닥과 붙어있을 것이다.
따라서 맵의 바닥에 있는 모든 미네랄을 시작으로 BFS를 통하여 방문한 뒤에(상하좌우), 방문했음을 기록한다.
public static int findClusterFromBottom() {
visited = new boolean[R][C];
int blocks = 0;
for (int i = 0; i < C; i++) {
// 바닥의 미네랄 위치에서 탐색한다
if (map[0][i] != 'x') {
continue;
}
Queue<int[]> adjacent = new LinkedList<>();
adjacent.add(new int[] {0, i});
while (!adjacent.isEmpty()) {
int[] current = adjacent.poll();
for (int[] a : around) {
int aroundRow = current[0] + a[0];
int aroundCol = current[1] + a[1];
if (isValid(aroundRow, aroundCol) && !visited[aroundRow][aroundCol]
&& map[aroundRow][aroundCol] == 'x') {
visited[aroundRow][aroundCol] = true;
blocks++;
adjacent.add(new int[] {aroundRow, aroundCol});
}
}
}
}
return blocks;
}만약 공중에 떠있는 클러스터라면, 해당 클러스터를 바닥 미네랄을 시작으로 방문할 수 없을 것이고
이는 map에는 'x'(미네랄) 인데, visited는 false(방문하지 않음) 이라면 공중에 떠있는 클러스터라고 판단할 수 있을 것이다.
이 메서드를 통하여 visited 상태를 최신화하고, 바닥을 기준으로 이루어진 정상적인 위치의 클러스터 내의 칸의 개수를 리턴한다.
if (minerals != findClusterFromBottom()) {
// 공중에 떠있는, 분리된 클러스터를 찾는다
List<int[]> cluster = findSeperatedCluster();
// 클러스터가 얼마나 바닥으로 떨어져야 하는지 계산한다
int moveSize = findMoveSizeToBottom(cluster);
// 만약 1칸 이상 떨어져야 한다면 이동시킨다
if (moveSize > 0) {
moveCluster(cluster, moveSize);
}
}minerals 는 입력 당시 미네랄의 개수를 센 값이며, findClusterFromBottom() 은 직전 메서드에서 리턴받은 바닥을 기준으로 이루어진 클러스터 칸 개수이다.
이 값이 서로 다르다는 것은, 어딘가에 분리된 클러스터가 존재한다는 것으로 해석할 수 있다.
따라서 이 경우 공중에 떠있는 클러스터 집합(칸들)을 위에서 말한
"이는 map에는 'x'(미네랄) 인데, visited는 false(방문하지 않음) 이라면 공중에 떠있는 클러스터라고 판단할 수 있을 것이다."
를 통하여 파악하는 과정을 거친다.
public static List<int[]> findSeperatedCluster() {
List<int[]> seperated = new ArrayList<>();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] == 'x' && !visited[i][j]) {
seperated.add(new int[] {i, j});
}
}
}
return seperated;
}
다음 과정이다. 분리된 클러스터(분홍)는 기존 클러스터(노랑) 혹은 바닥까지 내려와야 한다(테트리스를 생각하면 쉽다)
분리된 클러스터(분홍)의 각 열의 가장 바닥부분(초록)이 바닥 혹은 다른 클러스터의 위에 닿을 때까지 내려야 하며, 어떠한 열이든 닿았다면 더이상 이동하지 않아야 하므로,
- 분리된 클러스터의 바닥 부분(초록)의 위치를 구하는 연산
- 바닥 부분(초록)에서 바닥 혹은 다른 클러스터까지의 최소 거리(5, 4, 1) 를 구하는 연산
- 그 중에서 최소인 1을 구해서 리턴
다음 과정을 통하여 해당 클러스터를 얼마나 아래로 내려야 하는 지 구할 수 있다.
public static int findMoveSizeToBottom(List<int[]> cluster) {
int[] clusterBottoms = new int[C];
// 클러스터를 아래쪽으로 이동시키기 위해 가장 바닥 칸의 위치를 구함
for (int i = 0; i < C; i++) {
clusterBottoms[i] = R;
}
for (int[] current : cluster) {
clusterBottoms[current[1]] = Math.min(clusterBottoms[current[1]], current[0]);
}
int moveTo = R;
for (int i = 0; i < C; i++) {
if (clusterBottoms[i] != R) {
int count = 0;
for (int j = clusterBottoms[i] - 1; j >= 0; j--) {
if (map[j][i] == 'x') {
break;
}
count++;
}
moveTo = Math.min(moveTo, count);
}
}
return moveTo;
}
이 과정이 끝나면, 얼마나 내려야 하는지와 해당 클러스터 집합을 알고 있으므로 이를 바탕으로 클러스터를 아래로 내려주면 된다.
public static void moveCluster(List<int[]> cluster, int moveSize) {
for (int[] current : cluster) {
map[current[0] - moveSize][current[1]] = 'x';
map[current[0]][current[1]] = '.';
}
}
문제를 이해하는 게 힘들기도 했고, 코드 자체도 길어서 쉽게 풀수 있었던 문제는 아니었다는 생각이 든다.
다만 이런 것을 생각할 때 먼저 예시를 통하여 이해하는 것이 도움이 많이 되는 것 같다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static char[][] map;
static int R;
static int C;
static int minerals;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
minerals = 0;
for (int i = R - 1; i >= 0; i--) {
String input = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = input.charAt(j);
// 입력받을 때 미네랄의 개수를 카운팅한다
if (map[i][j] == 'x') {
minerals++;
}
}
}
int N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int height = Integer.parseInt(st.nextToken());
// 입력받는 높이는 1부터 시작하고, 배열은 0부터 시작하므로 1을 빼준다.
int[] hited = findHit(height - 1, i % 2 == 0);
// findHit은 부순 미네랄이 없을 경우 null을 리턴하여 아래 구문이 실행되지 않는다.
if (Objects.nonNull(hited)) {
// 클러스터가 분리된 경우는 현재 미네랄의 개수와 클러스터에 해당하는 미네랄의 개수를 비교한다.
// 만약 공중에 떠있는 클러스터라면, findClusterFromBottom 에 의해 카운팅되지 않을 것이다
if (minerals != findClusterFromBottom()) {
// 공중에 떠있는, 분리된 클러스터를 찾는다
List<int[]> cluster = findSeperatedCluster();
// 클러스터가 얼마나 바닥으로 떨어져야 하는지 계산한다
int moveSize = findMoveSizeToBottom(cluster);
// 만약 1칸 이상 떨어져야 한다면 이동시킨다
if (moveSize > 0) {
moveCluster(cluster, moveSize);
}
}
}
}
print();
}
public static void moveCluster(List<int[]> cluster, int moveSize) {
for (int[] current : cluster) {
map[current[0] - moveSize][current[1]] = 'x';
map[current[0]][current[1]] = '.';
}
}
public static int findMoveSizeToBottom(List<int[]> cluster) {
int[] clusterBottoms = new int[C];
// 클러스터를 아래쪽으로 이동시키기 위해 가장 바닥 칸의 위치를 구함
for (int i = 0; i < C; i++) {
clusterBottoms[i] = R;
}
for (int[] current : cluster) {
clusterBottoms[current[1]] = Math.min(clusterBottoms[current[1]], current[0]);
}
int moveTo = R;
for (int i = 0; i < C; i++) {
if (clusterBottoms[i] != R) {
int count = 0;
for (int j = clusterBottoms[i] - 1; j >= 0; j--) {
if (map[j][i] == 'x') {
break;
}
count++;
}
moveTo = Math.min(moveTo, count);
}
}
return moveTo;
}
public static List<int[]> findSeperatedCluster() {
List<int[]> seperated = new ArrayList<>();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] == 'x' && !visited[i][j]) {
seperated.add(new int[] {i, j});
}
}
}
return seperated;
}
/**
* 막대를 height 높이로 던졌을 때, 맞는 미네랄의 좌표를 리턴하는 메서드
*
* @param height 막대를 던진 높이
* @param isLeft 왼쪽에서 던졌으면 true, 오른쪽에서 던졌다면 false
* @return 미네랄의 좌표, 아무것도 안맞았다면 null 반환
*/
public static int[] findHit(int height, boolean isLeft) {
if (isLeft) {
for (int i = 0; i < C; i++) {
if (map[height][i] == 'x') {
map[height][i] = '.';
minerals--;
return new int[] {height, i};
}
}
} else {
for (int i = C - 1; i >= 0; i--) {
if (map[height][i] == 'x') {
map[height][i] = '.';
minerals--;
return new int[] {height, i};
}
}
}
// 아무것도 맞지 않았을 경우에는 null 반환
return null;
}
public static void print() {
for (int i = R - 1; i >= 0; i--) {
for (int j = 0; j < C; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
static int[][] around = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
static boolean[][] visited;
public static int findClusterFromBottom() {
visited = new boolean[R][C];
int blocks = 0;
for (int i = 0; i < C; i++) {
// 바닥의 미네랄 위치에서 탐색한다
if (map[0][i] != 'x') {
continue;
}
Queue<int[]> adjacent = new LinkedList<>();
adjacent.add(new int[] {0, i});
while (!adjacent.isEmpty()) {
int[] current = adjacent.poll();
for (int[] a : around) {
int aroundRow = current[0] + a[0];
int aroundCol = current[1] + a[1];
if (isValid(aroundRow, aroundCol) && !visited[aroundRow][aroundCol]
&& map[aroundRow][aroundCol] == 'x') {
visited[aroundRow][aroundCol] = true;
blocks++;
adjacent.add(new int[] {aroundRow, aroundCol});
}
}
}
}
return blocks;
}
public static boolean isValid(int row, int col) {
return row >= 0 && row < R && col >= 0 && col < C;
}
}
Source Code on GitHub
댓글