[JAVA] 백준 2933 : 미네랄, 18500 : 미네랄2

문제

2933번: 미네랄

 

18500번: 미네랄 2

미네랄 2도 같은 코드로 해결 가능.

 

해결 방법

범위는 크지 않아서 문제에서 주어진대로 구현만 하면 된다.

처음에 문제가 이해가 잘 되지 않아서 내가 이해한 것을 바탕으로 최대한 풀어서 설명하려고 한다.

일단 문제에서 얘기하는 클러스터는 미네랄이 여러 개 뭉쳐있는 뭉치를 이야기하는 것이다.

자신의 상하좌우로 다른 미네랄이 있으면 그 미네랄과 자신은 하나의 뭉치가 되고 그것을 클러스터라고 문제에서 이야기하고 있다.

그 미네랄 뭉치들이 만약 땅에 붙어있지않다면 땅이나 다른 미네랄을 만날 때까지 아래로 떨어진다고 한다.

 

그래서 문제의 입력과 출력을 한 단계씩 표현한다면 다음과 같다.

크기를 맞추기 위해 빈칸은 ○, 미네랄은 ●로 표현하였다.

 

○○○○○○○○    ○○○○○○○○    ○○○○○○○○

○○○○○○○○    ○○○○○○○○    ○○○○○○○○

○○○●○●●○    ○○○●○●●○    ○○○○○●●○

○○○●●●○○    ○○○●●●○○    ○○○●●●○○

○○●●●○○○    ○○●●●○○○    ○○●●●○○○

○○●○●●●○    ○○●○●●●○    ○○●○●●●○

○○●○○○●○    ○○●○○○●○    ○○●○○○●○

○●●●○○●○    ○●●●○○●○    ○●●●○○●○

 

처음 상태부터 시작, 제거되는 부분은 파란색

 

○○○○○○○○    ○○○○○○○○

○○○○○○○○    ○○○○○○○○

○○○○○●○○    ○○○○○●○○

○○○●●●○○    ○○○●●●○○

○○●●●○○○    ○○○●●○○○

○○●○●●●○    ○○●○●●●○

○○●○○○●○    ○○●○○○●○

○●●●○○●○    ○●●●○○●○

 

여기서 3번 오른쪽 미네랄(파란색)이 제거 된 후에 빨간 부분이 공중에 떠 있는 미네랄 뭉치가 되게 된다.

제거 전까지는 상하좌우 중 우측편에 붙어서 같은 클러스터, 즉 미네랄 뭉치였기 때문에 바닥과 붙어있었는데,

사라지게 되면서 빨간 부분이 독립된 클러스터(미네랄 뭉치)가 되어 아래로 떨어지게 되는 상황이 되었다.

 

○○○○○○○○    ○○○○○○○○

○○○○○○○○    ○○○○○○○○

○○○○○○○○    ○○○○○○○○

○○○○○○○○    ○○○○○○○○

○○○○○●○○    ○○○○○●○○

○○●●●●○○    ○○●●●●○○

○○●●●○●○    ○○●●●○●○

○●●●●●●○    ○●●●●●●○

 

그렇게 떨어진 클러스터(미네랄 뭉치)는 바닥과 만나게 되어 위와 같은 모양을 형성하고

마지막으로 1번 왼쪽 미네랄이 제거되어 최종 출력과 같은 모양을 만들게 된다.

 

 

여기까지가 문제에 대한 설명이고, 구현은 다음과 같은 순서로 진행된다.

1. 막대기를 던져 좌측, 우측을 번갈아가며 미네랄을 파괴

2. 땅에 붙어 있는 클러스터(미네랄 뭉치)를 BFS로 탐색

3. 그 외 클러스터(미네랄 뭉치) 탐색, 공중에 떠 있는 클러스터(미네랄 뭉치)를 의미

4. 떠 있는 클러스터(미네랄 뭉치)를 List에 추가 후 빈 칸 ' . ' 으로 지정

5. List에 담긴 미네랄들을 한 칸씩 내리면서 아래가 땅이거나 미네랄일 경우 중지

6. List에 담긴 미네랄을 다시 동굴에 ' x ' 로 추가

 

상하좌우 탐색은 dx, dy 배열을 사용해서 탐색함.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {	
	static char cave[][];
	static int R, C;
	static boolean visit[][];
	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {1, -1, 0, 0};
	
	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());
		
		cave = new char[R][C];
		for (int i = 0; i < R; i++) {
			String a = br.readLine();
			for (int j = 0; j < C; j++) {
				cave[i][j] = a.charAt(j);
			}
		}
		
		int N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			int removePoint = Integer.parseInt(st.nextToken());
			removeMi(removePoint, i);
			visit = new boolean[R][C];
			mineralMove();
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				sb.append(cave[i][j]);
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
		
	}
	
	static void removeMi(int row, int cnt) {
		row = R - row;
		
		// 좌우를 반복하면서 제거 하기 때문에 홀수, 짝수를 이용해서 제거.
		if (cnt % 2 == 0) { 
			for (int i = 0; i < C; i++) {
				if (cave[row][i] == 'x') {
					cave[row][i] = '.';
					break; // 하나만 제거하고 막대기가 사라지기 때문에 바로 break;
				}
			}
		} else {
			for (int i = C - 1; i >= 0; i--) {
				if (cave[row][i] == 'x') {
					cave[row][i] = '.';
					break; // 하나만 제거하고 막대기가 사라지기 때문에 바로 break;
				}
			}
		}
	}
	
	static void mineralMove() {
		Queue<Node> q = new LinkedList<>();
		
		for (int j = 0; j < C; j++) { // 땅과 붙어있는 미네랄 bfs 탐색
			if (cave[R - 1][j] =='x' && !visit[R - 1][j]) {
				q.add(new Node(R - 1, j));
				visit[R - 1][j] = true;
			}
			
			while(!q.isEmpty()) {
				Node node = q.poll();
				
				for (int i = 0; i < 4; i++) {
					int newX = node.x + dx[i];
					int newY = node.y + dy[i];
					
					if (isRange(newX, newY) && cave[newX][newY] == 'x' && !visit[newX][newY]) {
						// 동굴의 범위 안이고, 미네랄이고, 방문하지 않았을 경우.
						q.add(new Node(newX, newY));
						visit[newX][newY] = true;
					}
				}
			} // 여기까지 끝나면 땅과 붙어있는 미네랄들이 모두 정리됨.
		}
		
		// 공중에 떠있는 미네랄 찾기
		// 두 개 이상의 클러스터가 동시에 떨어지는 경우가 없어서 가능한 코드.
		ArrayList<Node> airMi = new ArrayList<>();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (cave[i][j] == 'x' && !visit[i][j]) {
					airMi.add(new Node(i, j));
					cave[i][j] = '.';
					visit[i][j] = true;
					// 공중에 떠 있는 미네랄들을 모두 넣어줌.
					// 이동할 것이기 떄문에 .로 바꿔둠.
				}
			}
		}
		
		// 공중에 떠있는 미네랄이 있다면 ~
		if (!airMi.isEmpty()) {
			boolean isStop = false;
			
			while (!isStop) {
				for (int i = 0; i < airMi.size(); i++) {
					int nextX = airMi.get(i).x + 1;
					if (nextX >= R || cave[nextX][airMi.get(i).y] =='x') {
						isStop = true;
						break;
					}
				} // 전체 미네랄이 아래로 한칸 내려갈 수 있는지 확인.
				
				if(!isStop) {
					for (Node node : airMi) {
						node.x++;
						// 내려갈 수 있다면 전체 미네랄을 한칸 내린 좌표를 다시 입력해줌.
					}
				}
			}
			
			// 최대로 내린 미네랄들을 다시 동굴에 입력 해줌.
			for (int i = 0; i < airMi.size(); i++) {
				cave[airMi.get(i).x][airMi.get(i).y] = 'x';
			}
		}
	}
	
	static boolean isRange(int x, int y) {
		if (x < 0 || x >= R || y < 0 || y >= C) {
			return false;
		}
		
		return true;
	}
}

class Node {
	int x;
	int y;
	
	Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}