백준 2933번 : 미네랄 | JAVA

 

📌 알고리즘 선택

정말 어려운 문제였다 ... 사실 알고리즘 문제는 30분 안에 해결하지 못했을 경우, 풀이를 보고 마무리 하는 것이 가장 이상적이라고 알려져 있지만 이 문제는 며칠을 붙잡고 본 것 같다. 흑흑

 

우선, 문제를 해결하기 위한 단계를 정리해보자.

1. 주어진 높이와 방향의 미네랄 파괴
2. 파괴된 시점에서 클러스터가 공중에 떠있는지 확인
3. 클러스터가 공중에 떠있다면 밑으로 내릴 수 있을 때까지 내리기

위 작업을 N번(막대를 던진 횟수)만큼 반복해주면 된다.

 

클러스터를 알아내기 위해 BFS를 사용할 수 있으며, 나머지는 모두 구현이라고 볼 수 있을 것 같다.

 

---

📌 풀이

위에서 언급한 바와 같이, 이 문제는 3단계를 N번(막대를 던진 횟수)만큼 반복해주면 된다.

1. 주어진 높이와 방향의 미네랄 파괴
2. 파괴된 시점에서 클러스터가 공중에 떠있는지 확인
3. 클러스터가 공중에 떠있다면 밑으로 내릴 수 있을 때까지 내리기

 

1번 단계의 경우, 'x'를 만났을 때 '.'로 바꿔주면 되기에 꽤 간단한 작업이다.

 

2번 단계가 까다로운데, 우선 클러스터를 찾기 위해 BFS를 사용하였다. 그리고 클러스터를 이루는 미네랄의 row 위치를 확인하여, 최댓값(가장 낮은 위치)가 R-1이 아닌 경우 공중에 떠있다고 판단하고 3번 단계로 넘어가도록 하였다.

문제에서 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우는 없다고 명시하였기 때문에 하나의 떠있는 클러스터를 발견하면 더이상 찾아보지 않고 return 하자.

 

3번 단계의 경우, 몇 칸을 내릴 수 있는지 먼저 판단해야 한다. 우선 원래 자리에 있는 클러스터를 모두 '.'으로 바꿔 지운다. 그리고 한 칸씩 내려보면서 바닥이나 다른 미네랄과 닿을 경우 더이상 내려갈 수 없다고 판단하고, 내려갈 수 있는 칸 수를 결정했다. 해당 클러스터를 모두 지운 상태이기 때문에, 내릴 수 있는 칸 수 만큼 내려서 다시 '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 class Loc {
        int i;
        int j;

        public Loc(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    static int height;
    static int width;
    static char[][] graph;
    static int[][] clusters;
    static int stick;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());
        graph = new char[height][width];

        for(int i = 0; i < height; i++) {
            graph[i] = br.readLine().toCharArray();
        }

        int chance = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < chance; i++) {
            stick = Integer.parseInt(st.nextToken());
            destroyMineral(stick, i%2==0?1:2);
            setCluster();
        }

        // 결과 출력
        for(int i = 0; i < height; i++) {
            System.out.println(graph[i]);
        }

    }

    public static void destroyMineral(int stick, int dir) {

        // dir이 1이면 왼쪽
        if(dir == 1) {
            for(int i = 0; i < width; i++) {
                if(graph[height-stick][i] == 'x') {
                    graph[height-stick][i] = '.';
                    return;
                }
            }
        }

        // dir이 2이면 오른쪽
        else {
            for(int i = width-1; i >=0; i--) {
                if(graph[height-stick][i] == 'x') {
                    graph[height-stick][i] = '.';
                    return;
                }
            }
        }

    }

    public static void setCluster() {

        clusters = new int[height][width]; // 0으로 초기화 됨
        int clusterNum = 1;
        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                if(graph[i][j] == 'x' && clusters[i][j] == 0) {
                    // 떠있는 클러스터를 발견할 경우
                    if(findCluster(i, j, clusterNum))
                        return;
                    clusterNum++;
                }
            }
        }

    }

    public static boolean findCluster(int i, int j, int clusterNum) {

        int[] di = {0, 0, -1, 1};
        int[] dj = {1, -1, 0, 0};

        int lowest = -1;

        Queue<Loc> q = new LinkedList<>();
        ArrayList<Loc> arr = new ArrayList<>();

        q.add(new Loc(i, j));
        clusters[i][j] = clusterNum;

        // bfs로 클러스터 찾기
        while(!q.isEmpty()) {
            Loc now = q.poll();
            lowest = Math.max(lowest, now.i);

            for(int d = 0; d < 4; d++) {
                int ni = now.i + di[d];
                int nj = now.j + dj[d];

                if(ni < 0 || nj < 0 || ni >= height || nj >= width)
                    continue;

                if(clusters[ni][nj] == 0 && graph[ni][nj] == 'x') {
                    clusters[ni][nj] = clusterNum;
                    q.add(new Loc(ni, nj));
                }
            }

            // 하나의 클러스터가 arr
            arr.add(now);

        }

        // 클러스터의 가장 아래가 바닥과 맞닿아있지 않을 경우, 클러스터 이동
        if(lowest != height-1) {
            moveCluster(arr);
            return true;
        }

        return false;

    }

    public static void moveCluster(ArrayList<Loc> arr) {

        int move = 1;

        // 원래 자리에 있는 클러스터 지우기
        for(Loc loc : arr) {
            graph[loc.i][loc.j] = '.';
        }

        outerLoop:
        while(true) {
            for(Loc loc : arr) {
                // 밑으로 한칸 내렸을 때 바닥 넘어가거나 다른 클러스터랑 겹치기 전까지만 내리기
                if(loc.i + move == height || graph[loc.i + move][loc.j] == 'x') {
                    move--;
                    break outerLoop;
                }
            }
            move++;
        }

        // 업데이트
        for(Loc loc : arr) {
            graph[loc.i + move][loc.j] = 'x';
        }

    }

}