[BOJ/Java] 2933. 미네랄

[BOJ/Java] 2933. 미네랄

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

---

🔍 문제 분석

백준 2933번 "미네랄" 문제는 2차원 격자 형태의 동굴에서 막대를 던져 미네랄을 부수고, 이후 클러스터(공중에 떠 있는 미네랄 조각들)의 중력을 적용하는 시뮬레이션 문제이다.

문제를 단계별로 분석하면 다음과 같다:

1. 입력
   • 동굴의 크기 R×C (최대 100×100)
   • 동굴 내 미네랄('x')과 빈 공간('.') 정보
   • 막대를 던지는 횟수 N
   • 각 막대를 던지는 높이 정보
2. 막대가 부딪히는 미네랄 제거
   • 왼쪽에서 던지는 경우는 왼쪽부터 탐색하며 'x'를 제거
   • 오른쪽에서 던지는 경우는 오른쪽부터 탐색하며 'x'를 제거
3. 클러스터 검출 및 중력 적용
   • 미네랄이 부서진 후, 공중에 떠 있는 클러스터를 찾아 중력을 적용한다.
   • BFS/DFS를 활용하여 바닥과 연결된 클러스터를 찾고, 나머지를 떨어뜨린다.
   • 떨어질 높이는 바닥 또는 다른 미네랄과 가장 가까운 거리로 계산한다.

🚀 풀이 과정

1. 동굴 맵을 입력받고, 각 단계별로 막대를 던진다.
2. 막대가 미네랄을 제거한 후, 클러스터가 떠 있는지 확인한다.
   • BFS를 이용하여 바닥과 연결된 미네랄을 찾는다.
   • 연결되지 않은 클러스터는 중력으로 떨어뜨린다.
3. 중력 적용 후 동굴 상태를 갱신한다.
4. 모든 막대 투척이 끝나면 최종 동굴 상태를 출력한다.

💻 코드 구현

아래는 Java로 구현한 코드이다.

import java.io.*;
import java.util.*;

public class Main {
    static int R, C;
    static char[][] map;
    static int[] dx = {0, 0, -1, 1}; // 좌, 우, 상, 하
    static int[] dy = {-1, 1, 0, 0}; 
    static boolean[][] visited;
    
    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++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
            }
        }
        
        // 막대 던지는 횟수
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < N; i++) {
            int height = Integer.parseInt(st.nextToken());
            throwStick(R - height, i % 2 == 0); // 높이 변환
            applyGravity();
        }
        
        // 결과 출력
        printMap();
    }
    
    // 막대 던지기
    static void throwStick(int h, boolean leftToRight) {
        if (leftToRight) {
            for (int i = 0; i < C; i++) {
                if (map[h][i] == 'x') {
                    map[h][i] = '.';
                    return;
                }
            }
        } else {
            for (int i = C - 1; i >= 0; i--) {
                if (map[h][i] == 'x') {
                    map[h][i] = '.';
                    return;
                }
            }
        }
    }
    
    // 중력 적용
    static void applyGravity() {
        visited = new boolean[R][C];
        
        // 바닥과 연결된 클러스터 찾기
        for (int i = 0; i < C; i++) {
            if (map[R - 1][i] == 'x' && !visited[R - 1][i]) {
                bfs(R - 1, i);
            }
        }
        
        // 공중에 떠 있는 클러스터 확인
        List<int[]> floating = new ArrayList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'x' && !visited[i][j]) {
                    floating.add(new int[]{i, j});
                    map[i][j] = '.'; // 미리 제거
                }
            }
        }
        
        if (floating.isEmpty()) return;

        // 얼마나 내려갈 수 있는지 확인
        int dropHeight = R;
        for (int[] cell : floating) {
            int x = cell[0], y = cell[1];
            int h = 0;
            while (x + h + 1 < R && map[x + h + 1][y] == '.') {
                h++;
            }
            dropHeight = Math.min(dropHeight, h);
        }

        // 클러스터를 떨어뜨림
        for (int[] cell : floating) {
            map[cell[0] + dropHeight][cell[1]] = 'x';
        }
    }

    // BFS를 사용하여 바닥과 연결된 클러스터 찾기
    static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d], ny = cur[1] + dy[d];
                if (nx >= 0 && ny >= 0 && nx < R && ny < C && map[nx][ny] == 'x' && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
    
    // 최종 맵 출력
    static void printMap() {
        StringBuilder sb = new StringBuilder();
        for (char[] row : map) {
            sb.append(row).append("\n");
        }
        System.out.print(sb);
    }
}

---

⏳ 시간 복잡도 분석

• 막대 던지기: O(C)
• BFS 탐색: O(RC)
• 중력 적용: O(RC)

따라서 전체 시간 복잡도는 O(N × RC) 정도로, 최악의 경우 (100×100)에서도 100만 번 정도의 연산이므로 충분히 실행 가능하다.

---

🤔 느낀점

• BFS와 시뮬레이션을 조합하는 문제였다.
• 중력을 적용하는 과정에서 최소 몇 칸을 내려갈 수 있는지 계산하는 방법이 핵심이었다.
• visited 배열을 활용하여 바닥과 연결된 클러스터를 빠르게 찾는 전략이 중요했다.
• 시간이 오래 걸릴 수 있는 부분을 List<int[]>를 활용하여 최적화했다.

이 문제를 풀면서 시뮬레이션 문제에서의 BFS 활용법을 더 깊이 익힐 수 있었다. 🚀