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

문제

2933번: 미네랄

풀이

이 문제의 풀이를 요약하자면 아래와 같다. 

 

1. 왼쪽, 오른쪽 번갈아서 미네랄 파괴

2. 미네랄 파괴 후 공중에 떠있는 클러스터 BFS로 찾기

3. 공중에 떠있는 클러스터들을 아래로 내리기

 

먼저, 1번을 구현하는 것은 쉽다. 단순히 홀수, 짝수를 나누어 왼쪽에서부터 탐색, 오른쪽에서부터 탐색해서 'x'를 '.'으로 바꿔주기만 하면 된다.

 

2번을 구현하는 것은 조금 까다롭다. 우선 '공중에 떠있다'라는 것은 클러스터가 땅에 붙어있지 않다는 것을 의미한다. 이것은 BFS를 통해 찾을 수 있는데, 가장 아래 땅에서부터 BFS탐색을 진행하면 땅에 붙어있는 클러스트들을 찾을 수 있다. 따라서 BFS를 통해 땅에 붙어있는 클러스트들을 visited[][] 배열을 이용해 방문처리를 해주고, 이후 방문처리가 안되어있는 클러스트를 따로 저장하면 된다.

 

3번은 2번에서 따로 저장한 공중에 떠있는 클러스트들의 세로 좌표를 1씩 올리고 범위를 벗어나지 않는지만 체크하면 된다. 모든 좌표를 수정한 후 map[][]의 원소를 'x'로 수정해주면 완료이다.

 

코드

 

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;
 
public class Main {
 
    static int r,c,n;
    static char[][] map;
    static boolean[][] visited;
    static Queue<Node> q = new LinkedList<>();
    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());
        
        map = new char [r][c];
        
        for (int i = 0; i < r; i++) {
            map[i] = br.readLine().toCharArray();
        }
        
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) {
            int h = r-Integer.parseInt(st.nextToken());
           
            breakMineral(h,i);    // 미네랄 파괴
            bfs();    // 클러스터 내리기
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < r; i++) {
            sb.append(map[i]);
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }
    
    static void bfs() {
        visited = new boolean[r][c];
        ArrayList<Node> cluster = new ArrayList<>();
        
        // 땅에 붙어있는 클러스터들을 방문처리
        for (int j = 0; j < c; j++) {
            if(map[r-1][j] =='.' || visited[r-1][j])
                continue;
            
            visited[r-1][j] = true;
            q.add(new Node(r-1, j));
            
            while(!q.isEmpty()) {
                Node cur = q.poll();
                
                for (int i = 0; i < 4; i++) {
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];
                    
                    if(!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] =='.')
                        continue;
                    
                    visited[nx][ny] = true;
                    q.add(new Node(nx, ny));
                }
            }
        }
        
        // 공중에 떠 있는 클러스터 찾기 == 방문처리가 안되어 있는 클러스터 찾기
        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 Node(i, j));
                }
            }
        }
        
        // 공중에 뜬 클러스터가 없으면 return
        if(cluster.isEmpty()) {    
            return;
        }
        
        // 클러스터 내리기
        boolean down = true;
        while(down) {
            for(Node node : cluster) {
                int nx = node.x +1;
                int ny = node.y;
                
                if(!isRange(nx, ny) || map[nx][ny] == 'x') {
                    down = false;
                    break;
                }
            }
            if(down) {
                for(Node node : cluster) {
                    node.x++;
                }
            }
        }
        
        // map 원소 변경
        for(Node node : cluster) {
            map[node.x][node.y] = 'x';
        }
        
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= r || y < 0 || y >= c) return false;
        return true;
    }
    
    static void breakMineral (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;
                }
            }
        }
    }
    
    static class Node {
        int x;
        int y;
        
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
}

결과