[백준] 2933 미네랄, java

https://www.acmicpc.net/problem/2933

 

문제 이해

문제 설명은 다음과 같습니다. 간단하게 정리해 보겠습니다.

 

1. '.'과 'x'로 이루어진 map을 줍니다.

2. N 횟수만큼 막대를 좌, 우에서 한 번씩 던져 x를 제거합니다.

3. x가 제거될 때, 상하좌우에 인접한 미네랄이 끊어질 경우, 중력이 작용하여 미네랄 덩어리는 바닥으로 떨어집니다.

4. 막대를 모두 던진 후 map의 모습을 출력합니다.

 

다음은 문제에 접근한 방법을 서술해 보겠습니다. 처음에는 잘못된 방법으로 문제를 풀고 있었으며, 다행히 이를 바로잡기 쉽게 문제를 접근하고 있었습니다. 덕분에 문제점을 발견하고 빠르게 정정하여 문제를 풀어낼 수 있었습니다.

 

첫 번째 풀이

1. 먼저 미네랄의 개수를 모두 세주었습니다.

2. 이후 막대 하나씩 던지며, 미네랄을 지워줍니다.

3. bfs를 이용해 상하좌우로 연결되어 있는 막대를 파악한 뒤, 현재 전체 막대의 개수와 일치하지 않는다면 분리가 발생한 것이라고 판단했습니다. 또 입력의 설명 부분에서 "두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다."라는 부분을 보고 분리가 이루어졌다면 바닥에 인접해있지 않은 클러스터와 아닌 클러스터를 구분하여 아닌 클러스터에 중력을 적용시키면 되겠다.라는 생각을 하게 되었습니다.

4. 다음은 중력을 적용시키는 방법입니다. 저는 떨어져야 할 클러스터의 미네랄 중에 가장 하단에 있는 미네랄들의 위치만을 찾은 뒤, 해당 미네랄들만 아래로 1씩 감소시켜 가장 먼저 멈추게 되는 미네랄을 찾았고, 그 미네랄이 움직인 거리를 구하였습니다.

5. 그리고 그 거리만큼 떨어져야 할 클러스터들을 모두 아래로 이동시키는 방식으로 해결해 내었습니다.

 

위의 풀이대로 문제를 풀었고, 기본으로 주어지는 예제는 모두 해결할 수 있었습니다.

그리고 신난 마음에 제출을 진행하였는데, 몹시 빠르게 틀렸습니다를 보여주는 슬픈 상황을 보게 됩니다.

 

이후 다른 테스트케이스를 찾아보며 테스트를 해본 결과 첫 번째 풀이의 3번 부분인 분리를 확인하는 부분이 잘못됨을 확인할 수 있었습니다. 미네랄이 제거되며 분리된 두 개의 클러스터 모두 바닥에 인접해 있다면 잘못된 판단을 하게 됩니다.

 

따라서 미네랄의 개수를 이용해 분리를 판단하지 않고, 미네랄을 지우고 map의 상단부터 확인하며 발견되는 클러스터가 공중에 떠있다면, 그 클러스터를 바로 중력을 적용시키는 방식으로 진행했습니다. 그 외에는 크게 어려운 부분 없이 문제를 해결했습니다.

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_BJ_02933_G1_미네랄 {
	static int Y, X;
	static int[] dy = {0,0,-1,1};
	static int[] dx = {-1,1,0,0};
	static char[][] board;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Y = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());

		board = new char[Y][X];
		int idx = Y-1; //쉽게 하기 위해 거꾸로 쌓아줍니다.
		for (int i = 0; i < Y; i++) {
			String line = br.readLine();
			board[idx--] = line.toCharArray();
		}

		int cnt = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < cnt; i++) {

			//1.미네랄을 지워줍니다.
			int now = Integer.parseInt(st.nextToken())-1;
			if(i%2==0){
				for (int j = 0; j < X; j++) {
					if(board[now][j] == 'x'){
						board[now][j] = '.';
						break;
					}
				}
			} else {
				for (int j = X-1; j >= 0; j--) {
					if(board[now][j] == 'x'){
						board[now][j] = '.';
						break;
					}
				}
			}
			gravity();
		}

		//StringBuilder를 이용해 결과값을 만들어 출력합니다.
		StringBuilder sb = new StringBuilder();
		for (int i = Y-1; i >= 0; i--) {
			for (int j = 0; j < X; j++) {
				sb.append(board[i][j]);
			}
			sb.append("\n");
		}

		System.out.println(sb.toString().trim());
	}

	//중력을 적용합니다.
	static void gravity(){
		Queue<int[]> q = new LinkedList<>();
		boolean[][] visited = new boolean[Y][X];
		ArrayList<int[]> temp = new ArrayList<>();
		ArrayList<int[]> botList = new ArrayList<>();

		//맵을 위에서 부터 돌며, 클러스터를 찾고, 바닥에 인접해있지 않은 클러스터를 찾으면 증력을 적용하고
		//아니라면 중력을 적용하지 않습니다.
		boolean keep = false;
		for(int i=Y-1; i>=0; i--){
			for(int j=0; j<X; j++){
				boolean bot = false;
				if(!visited[i][j] && board[i][j] == 'x'){
					temp = new ArrayList<>();

					q.add(new int[]{i, j});
					visited[i][j] = true;

					while(!q.isEmpty()){
						int[] now = q.poll();
						temp.add(now);
						if(now[0] == 0) bot = true;
						for (int k = 0; k < 4; k++) {
							int ny = dy[k]+now[0];
							int nx = dx[k]+now[1];
							if(0<=ny && ny<Y && 0<=nx && nx<X && !visited[ny][nx] && board[ny][nx] == 'x'){
								q.add(new int[]{ny, nx});
								visited[ny][nx] = true;
							}
						}
					}

					if(!bot) {
						botList = temp;
						keep = true;
						break;
					}
				}
			}
		}

		if(!keep) return;

		Collections.sort(botList, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0]-o2[0];
			}
		});

		//현재 클러스터의 가장 하단에 있는 미네랄들의 높이를 찾아냅니다.
		int[] minList = new int[X];
		Arrays.fill(minList, 101);

		for(int[] now : botList){
			int ny = now[0];
			int nx = now[1];
			minList[nx] = Math.min(minList[nx], ny);
		}

		//현재 클러스터가 몇칸이나 내려가야 할지 한 칸씩 내려보며 h를 찾아냅니다.
		int h = 0;
		run : while(true){
			for(int i=0; i<X; i++){
				if(minList[i] == 101) continue;
				int ny = minList[i];
				if(ny-1 < 0 || board[ny-1][i] == 'x') {
					break run;
				}
				minList[i] = ny-1;
			}
			h++;
		}

		for(int[] now : botList){
			int ny = now[0];
			int nx = now[1];

			board[ny][nx] = '.';
			board[ny-h][nx] = 'x';
		}
	}
}