[백준 - Java] 2933번 : 미네랄

문제

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

설명

문제 이해하는 데 엄청 오래 걸렸던 문제..
bfs를 이용해 문제를 해결하였고, 조건만 잘 읽으면 나름 금방 풀 수 있는 문제였다.

주의할 점

1. 땅에 있는 클러스터를 확인한 후에 공중에 떠 있는 클러스터를 확인하는 것
2. 공중에 떠 있는 클러스터를 ArrayList에 저장할 때 'x'를 '.'로 바꿔주는 것 -> 'x'를 '.'로 바꿔주지 않고 클러스터가 떨어지는 것을 확인할 경우 공중에 떠 있는 클러스터도 포함된다. 그래서 클러스터가 밑으로 떨어질 수 있는 경우에도 flag = false가 돼서 클러스터가 제대로 떨어질 수 없는 경우가 발생할 수 있기 때문에 '.'로 바꿔줘야 한다.

for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
        if (!visited[i][j] && map[i][j] == 'x') {
            cluster.add(new Mineral(i, j));
            map[i][j] = '.';
        }
    }
}

3. 클러스터 모양이 변하지 않고 그대로 떨어지는 것 -> 처음에 미네랄이 떨어질 때 모양이 변하지 않고 떨어지는 것을 고려하지 않았다. 그래서 범위를 벗어나지 않고 미네랄이 없는 경우에 클러스터가 다 떨어져서 답이 이상하게 나왔다.

처음에 작성한 코드

while (flag) {
    for (Mineral m : cluster) {
        int nx = m.x + 1;
        int ny = m.y;
       
        if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] == '.') {
       	    m.x++;
        }
        else {
            flag = false;
            break;
         }
     }	
}

소스코드

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

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

public class Main {
    static int[] dx = {-1, 0, 1, 0}; // 상좌
    static int[] dy = {0, -1, 0, 1}; // 하우
	
    static int R, C;
    static char[][] map;

    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];
		
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }
		
        int N = Integer.parseInt(br.readLine()); // 막대를 던진 횟수
        st = new StringTokenizer(br.readLine());
		
        for (int i = 0; i < N; i++) {
        // 막대기 높이 -> 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미하므로 R에서 빼줌
            int height = R - Integer.parseInt(st.nextToken());
			
            throwStick(height, i);
            dropCluster();
        }
		
        for (int i = 0; i < R; i++) {
            System.out.println(map[i]);
        }
    }
	
    // 막대 던지기
    public static void throwStick(int row, int dir) {
        // 왼쪽에서 막대기를 던질 경우
        if (dir % 2 == 0) {
            for (int i = 0; i < C; i++) {
                // 미네랄이 있는 경우 파괴
                if (map[row][i] == 'x') {
                    map[row][i] = '.';
                    break; // 막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춤
                }
            }
        }
        else { // 오른쪽에서 막대기를 던질 경우
            for (int i = C - 1; i >= 0; i--) {
                if (map[row][i] == 'x') {
                    map[row][i] = '.';
                    break;
                }
            }
        }
    }
    
    // 클러스터 떨어뜨리기
    public static void dropCluster() {
        boolean[][] visited = new boolean[R][C];
        Queue<Mineral> q = new LinkedList<>();
		
        // 땅에 있는 미네랄 클러스터 체크
        for (int i = 0; i < C; i++) {
            if (map[R - 1][i] == 'x' && !visited[R - 1][i]) {
                visited[R - 1][i] = true;
                q.add(new Mineral(R - 1, i));
				
                while (!q.isEmpty()) {
                    Mineral mineral = q.poll();
					
                    // 상하좌우를 탐색하면서 땅에 있는 클러스터를 체크
                    for (int j = 0; j < 4; j++) {
                        int nx = mineral.x + dx[j];
                        int ny = mineral.y + dy[j];
						
                        if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                            if (map[nx][ny] == 'x' && !visited[nx][ny]) {
                                visited[nx][ny] = true;
                                q.add(new Mineral(nx, ny));	
                            }
                        }
                    }
                }
            }
        }
		
        // 공중에 떠 있는 미네랄 클러스터를 저장하기 위한 리스트
        ArrayList<Mineral> cluster = new ArrayList<>();
		
        // 공중에 떠 있는 미네랄 클러스터 체크
        // 위의 for문에서 탐색되지 못한 클러스터는 공중에 있는 것임
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (!visited[i][j] && map[i][j] == 'x') {
                    cluster.add(new Mineral(i, j));
                    map[i][j] = '.';
                }
            }
        }
		
        // 공중에 떠 있는 미네랄 클러스터가 없을 경우 종료
        if (cluster.isEmpty()) {
            return;
        }
		
        boolean flag = true;
		
        // 미네랄 클러스터를 떨어뜨릴 수 있는지 확인(아래 행에 클러스터가 있는지 없는지 확인)
        while (flag) {
            for (Mineral m : cluster) {
                int nx = m.x + 1; // 밑으로 내릴 수 있는지 확인하기 위해 +1을 하는 것
                int ny = m.y;
				
                // 떨어지는 동안 클러스터의 모양은 변하지 않기 때문에 클러스터 중 하나라도 밑으로 내릴 수 없는 경우 flag = false로 바꿔줌
                if (nx < 0 || nx >= R || ny < 0 || ny >= C || map[nx][ny] == 'x') {
                    flag = false;
                    break;
                }	
            }
			
            // 모든 클러스터가 밑으로 내려갈 수 있는 경우에만 위치를 바꿔줌
            if (flag) {
                for (Mineral m : cluster) {
                    m.x += 1;
                }
            }
        }
		
        // 미네랄 클러스터 떨어뜨리기
        for (Mineral m : cluster) {
            map[m.x][m.y] = 'x';
        }
		
    }
}

GITHUB

https://github.com/MinchaeKwon/BOJ/blob/master/BOJ%232933/src/Main.java