백준 2933. 미네랄 :: 돼지개발자

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

"조건을 잘 읽어보자. 슈발"

이 문제때문에 하루를 다날렸다. 문제를 이해하는데만 해도 굉장히 오랜 시간이 걸렸다. 

클러스터가 뭔데... 땅에 붙어 있는 미네랄에서 막대로 인해 부셔져 공중에 둥둥 떠 있는 미네랄 조각을 클러스터라 한다.

얼음 덩어리는 상,하,좌,우가 인접한 얼음의 집합이다. 그냥 막대를 던져 얼음 덩어리를 깼을 때, 생기는 각각의 얼음덩어리 중 상,하,좌,우가 지면과 맞닿아 있지 않는 얼음덩어리를 공중에 있다고 한다. 이렇게 공중에 있는 얼음덩어리는 중력에 의해 모양을 유지하며 아래로 떨어지게 되는데, 지면에 닿거나, 다른 얼음 덩어리를 만날 때 까지 떨어진다. (단, 떨어지는 얼음의 모양은 변하지 않는다. 즉, 덩어리로 떨어진다.)

그러니까 아래와 같다는 거다.

000111000    000000000

001111100    000111000

000111000    001111100

000010000    000111000

000010000 < 000010000

000111000    000111000

 내가 또 실수 했던 부분은 두개의 클러스터가 동시에 떨어지는 경우엔 어떻게 해야 하나라는 생각에서 배열 아래서부터 탐색해 먼저 나오는 얼음덩어리를 찾아서 처리해줘야하나? 등등 하루 왼종일 생각하다가

"두개 또는 그 이상의 클러스터가 동시에 떨어지는 경우는 없다" 라는 조건을 봤다.

우선 문제를 푼 방법은 던진 위치의  상, 하, 좌, 우 를 BFS를 통해 탐색한다. 4방향의 얼음덩어리를 탐색해 땅에 붙어 있지 않은 클러스터 한 개를 찾아낸다. 동시에 떨어지는 클러스터는 없다고 하였으니, 당연히 땅에 붙어 있지 않는 놈을 찾았다면 , 4방향 탐색은 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;
 
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 row = r-Integer.parseInt(st.nextToken());
            
            // 미네랄 파괴
            broke(row,i);
            // 클러스터 내리
            solve();
        }
        
        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 solve() {
        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));
                }
            }
        }
        
        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++;
                }
            }
        }
        
        // mark
        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 broke (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;
                }
            }
        }
    }
    
}
 
class Node {
    int x;
    int y;
    
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}