[백준 / BOJ] 18500 미네랄 2 (Java) / 2933 미네랄 1 포함

미네랄 2 기준으로 설명을 하겠다. (미네랄 1(2933번)과 2는 동일한 문제인데, 미네랄1이 테스트케이스가 좀더 빡샌거로 알고있다.)

실제로 동일 코드를 제출하면 모두 맞았습니다가 나온다.

미네랄 1

미네랄 2

---

문제

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

18500번: 미네랄 2

창영이와 상근이가 동굴을 놓고 소유권을 주장하고 있다.

 

두 사람은 막대기를 던져 싸우고있는데, 막대기가 날아가다 미네랄을 만나면, 해당 미네랄은 파괴되고 막대기도 이동을 멈춘다.

이때, 해당 미네랄이 속해있는 클러스터가 땅에서 분리되면(혹은 땅과 연결된 클러스터와 분리되면) 클러스터는 재결합할때까지 떨어진다.

 

창영이와 상근이가 막대기를 던지는 위치와 동굴의 초기상태가 주어졌을때, 모든 막대기를 던진후, 최종결과를 출력하는 문제다.

---

풀이

문제를 잘 이해하고 풀어야 했던 시뮬레이션 문제다.

(잘못 이해하고 풀었다가 디버깅에 코드고치는것만 1시간 걸렸다)

아래에서 다시 말하겠지만, 클러스트는 내려가는중에 자신의 아래에 바닥과 연결된 클러스트가 있으면 합쳐지는것임을 주의하자.

 

구현해야할 부분을 나눠보자.

 

1. 땅과 분리되어있는 클러스터 찾기

-> 이는 BFS를 통해 간단히 구현할수있다. 바닥에 닿아있는 미네랄부터 체크해간다. BFS가 종료되어있을때 체크되지않은 클러스터는 분리되어있다고 생각하면된다.

 

2. 클러스터 떨어트리기

-> 마찬가지로 바닥에서부터 떨어트리는데, 1번의 BFS결과에서 체크되지않은 미네랄을 전부 떨어트린다. 클러스터를 한칸씩 아래로 내려가며 다른 클러스터와 합쳐질수있는지 체크한다.

 

3. 클러스터 부수기

 

클러스터가 합쳐지는 조건을 잘 살펴보자.

클러스터가 내려가는 중간에 바닥에 닿은 클러스터와 닿으면 합쳐지는것이 아닌, 내려가는 중간에 자신의 아래에 다른 (바닥에 닿아있는)클러스터가 있으면 합쳐지는것이다.

이 조건을 사방으로 다른 클러스터와 닿아있다면 합쳐지는거라 생각하고 풀었다가 코드를 엎어야했다.

 

자신의 아래에 바닥과 연결된 클러스터가 있는지 유무는, 바텀업 DFS로 구현했다. 탐색중, 자신의 아래에 바닥과 연결된 클러스터가 있다면, true를 반환한다.

    private boolean mergeCluster(boolean[][] check, boolean[][] mergeCheck, int y, int x){
        if(check[y+1][x] || y == R) return true;
        mergeCheck[y][x] = true;
        boolean ret = false;
        for(int i = 0; i < 4; i++){
            int _y = y + dy[i];
            int _x = x + dx[i];
            if(_y > R || _y < 1 || _x > C || _x < 1 || mergeCheck[_y][_x] == true || check[_y][_x] == true || mineral[_y][_x] == '.') continue;
            ret = booleanMax(mergeCluster(check, mergeCheck, _y,_x),ret);
        }
        return ret;
    }

이때, 반환값이 true라면, 다시 바닥부터 시작해서 모든 클러스트를 합친다.

위 과정은 클러스트를 내리는 과정중 실행해줬다.

    private boolean[][] dropCluster(boolean[][] check){ // 호출할때마다 한칸 내린다
        int firstY = 0, firstX = 0;
        for(int y = R; y >= 1; y--){
            for(int x = 1; x <= C; x++){
                if(check[y][x] == true || mineral[y][x] == '.') continue;
                if(firstY == 0 && firstX == 0){
                    firstY = y;
                    firstX = x;
                }
                mineral[y][x] = '.'; // 이동 준비
                mineral[y+1][x] = 'x'; // 이동 
            }
        }
        boolean[][] mergeCheck = new boolean[R+5][C+5];
        if(mergeCluster(check, mergeCheck, firstY, firstX)){
            check = findCluster();
        }
        return check;
    }

아래의 조건문 안을 잘 보자.

        if(mergeCluster(check, mergeCheck, firstY, firstX)){

findCluster()를 호출하면 모든 클러스트를 합침과 동시에 새로운 check배열(합쳐진 클러스트 목록)을 반환한다.

 

위 두 코드를 총괄하는 코드(시뮬레이션 코드)는 아래와 같다.

    private void getMineral(int turn){
        if(turn > N) return;
        crushMineral(R-throwStick[turn]+1, turn%2);
        boolean[][] check = findCluster();
        while(!checkCluster(check)){
            check = dropCluster(check);
        }
        getMineral(turn+1);
    }

전체소스코드는 아래에있다.

(코드수정이 많아서 처음 구현보다 좀 더러워졌다..)

소스코드

https://github.com/devxb/JJUNalgo/blob/master/18500%20%EB%AF%B8%EB%84%A4%EB%9E%84%202/Main.java

devxb/JJUNalgo