[백준/JAVA] 2933번: 미네랄

📖 문제

2933번: 미네랄

 

 

 

💡  풀이 방식

• 구현, 시뮬레이션, BFS

필요 자료구조
- 4방 탐색용 dx/dy 배열
- 땅에 붙어있는 클러스터 위치 저장용 큐 (bfs 수행)
- 땅에 붙어있는 클러스터 표시할 방문 표시 배열
- 공중에 떠있는 미네랄 위치 저장용 리스트

 

 

1. 왼쪽, 오른쪽 번갈아가며 주어진 높이의 미네랄을 파괴한다.

private static void solve(int row, int i) {
    if(i % 2 == 0) {    // 왼 > 오
        for(int j = 0 ; j < C ; j++) {
            if(map[row][j] == 'x') {
                map[row][j] = '.';
                break;
            }
        }
    }
    else {  // 오 > 왼
        for(int j = C - 1 ; j >= 0 ; j--) {
            if(map[row][j] == 'x') {
                map[row][j] = '.';
                break;
            }
        }
    }
}

 

 

2. 파괴된 시점에서 클러스터 중 공중에 떠 있는 클러스터가 있는지 확인한다. (BFS)

→ 클러스터를 이루는 미네랄 中 하나라도 바닥에 닿아있으면 공중에 떠 있는 게 아님

= 클러스의 맨 아래 미네랄의 ROW 인덱스가 R-1 이 아니면 공중에 떠 있는 상태

 

> 맨 아래 땅에서부터 BFS 탐색해 땅에 붙어있는 클러스터들을 방문 처리하고, 이후 방문 처리 안 된 클러스터들(= 공중에 떠 있는 클러스터들)에 대해 따로 저장한다.

 

 

3. 공중에 떠 있는 클러스틀은 아래로 내린다.

 

> 2번에서 따로 저장한 공중에 떠 있는 클러스터들의 세로 좌표를 범위를 벗어나지 않는다면 1씩 올리고, 모든 좌표를 수정해 map의 원소를 x로 수정한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int R,C,N,H;
    static char[][] map;
    
    static Queue<int[]> q = new ArrayDeque<>();
    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 str = br.readLine();
            for(int j = 0 ; j < C; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        
        N = Integer.parseInt(br.readLine());    // 막대 던진 횟수
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            int height = Integer.parseInt(st.nextToken());
 
            solve(R - height, i);   // 1. 미네랄 지우기
            bfs();                  // 2. 클러스터 내리기
        }
        
        print();    // 출력하기
    }
    
    // 1. 미네랄 지우는 메서드
    private static void solve(int row, int i) {
        if(i % 2 == 0) {    // 왼 > 오
            for(int j = 0 ; j < C ; j++) {
                if(map[row][j] == 'x') {
                    map[row][j] = '.';
                    break;
                }
            }
        }
        else {  // 오 > 왼
            for(int j = C - 1 ; j >= 0 ; j--) {
                if(map[row][j] == 'x') {
                    map[row][j] = '.';
                    break;
                }
            }
        }
    }
    
    // 2. 클러스터 내리는 메서드
    private static void bfs() {
        visited = new boolean[R][C];
        
        for(int j = 0 ; j < C ; j++) { // 2-1) 땅에 붙은 클러스터들 방문처리하기
            if(map[R - 1][j] == '.' || visited[R - 1][j])   continue;
            
            visited[R - 1][j] = true;
            q.add(new int[]{R - 1, j});
            
            while(!q.isEmpty()) {
                int[] now = q.poll();
                
                for(int d = 0 ; d < 4 ; d++) {
                    int nx = now[0] + dx[d];
                    int ny = now[1] + dy[d];
                    
                    if(!inRange(nx, ny) || visited[nx][ny] || map[nx][ny] == '.') continue;
                    
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
        
        // 2-2) 공중에 떠있는 클러스터 찾기
        List<int[]> cluster = new ArrayList<>();
        
        for(int i = 0 ; i < R ; i++) {
            for(int j = 0 ; j < C ; j++) {
                if(!visited[i][j] && map[i][j] == 'x') {
                    map[i][j] = '.';
                    cluster.add(new int[] {i, j});
                }
            }
        }
        
        if(cluster.isEmpty())   return;
        
        // 2-3) 공중에 떠 있는 클러스터 내리기
        boolean down = true;
        while(down) {
            for(int[] now : cluster) {
                int nx = now[0] + 1; // 한 칸 아래로 내리기
                int ny = now[1];
                
                if(!inRange(nx, ny) || map[nx][ny] == 'x') {
                    down = false;
                    break;
                }
            }
            
            if(down) {
                for(int[] now : cluster) {
                    now[0]++;
                }
            }
        }
        
        // 2-4) 끌어내린 후 map 원소 변경하기
        for(int[] now : cluster) {
            map[now[0]][now[1]] = 'x';
        }
    }
    
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < R && 0 <= y && y < C;
    }
    
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(char[] c : map) {
            for(char h : c) {
                sb.append(h);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}
 

 

 

---

💦 어려웠던 점

- 단계를 쪼개서 빠르게 푸는 연습을 해야겄다,,,,

- 공중에 있는 클러스터를 어떻게 처리해서 끌어내리지?

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고... 2번째 글은 그림 설명 짱!

[백준] 2933_미네랄 (자바 풀이)

 

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