[JAVA]백준_2933_미네랄

 

문제링크

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

 

 

2933번: 미네랄

 

 

 

 

 

문제 이해가 잘 안되었다.

 

초반에는 계속 이어지고 이어지고?

십자가끼리 이어지다 보면 클러스터가 큰 한 뭉치라고 해야하나 그렇게 이해를 해서

도무지 이해가 안됐다.

 

 

그냥 사방향 인접하면 클러스터 1 로 하고 내려주고

다음 탐색해서 사방향 인접하면 클러스터 2 하고 내려주고

 

이렇게 하면 된다.

 

 

1. 높이 입력 받은 후 미네랄을 지워준다. 그리고 클러스터 찾아서 내려주는 과정 반복할 것이다.

 

 

 

 

2. height (높이), side(어느 방향으로 지울지) 를 매개변수로 받는다.

짝수는 왼쪽부터 지우고

홀수는 오른쪽부터 지우기 때문에

위에서 i%2로 넣어주었다.

 

 

 

 

3. 클러스터를 찾아주는 함수이다.

cnt를 통해 현재 클러스터가 몇번째 인지 표시해주었다.

 

배열 탐색 중 미네랄이면서 방문하지 않은 곳이면 클러스터를 찾아본다.

 

 

4.  현재 위치를 기준으로 찾는다.

low_height 변수에 땅과 가장 가까운 x 좌표를 저장해준다.

 

 

사방향 탐색하면서

미방문노드 && 미네랄이 위치 한 곳이면 방문표시해주고 큐에 넣어준다.

 

4방향탐색이 되어 클러스터가 완성이 되면 list 에 추가해준다.

 

 

혹시 가장 가까운 곳이 R-1인 경우 땅바닥과 맞닿아 있으므로 return false

아니면 이제 내려주기를 시작한다.

 

 

 

5. 일단 현재 내려줄 최소 단위는 1 (down = 1)

 

현재 ArrayList에 들어있는 노드들은 비워둔다. (나중에 내려야 될 것을 감안하여?)

 

그리고 이제 한 칸씩 밑으로 찾아보면서

땅바닥이거나 미네랄을 만나면 내려야될 높이를 조정하여준 후 (down--) loop문 탈출.

 

아닐 시 내릴 수 있는 높이를 크게 조정한다. (down++)

 

후 현재 내릴 수 있는 만큼 내린 곳에 미네랄을 채워준다.

 

<전체 코드>

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_2933 {
    static int R,C; //동굴의 크기
    static int N; //막대를 던진 횟수
    static char map[][];
    static int cluster[][];
    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++){
            String str = br.readLine();
            for(int j=0;j<C;j++){
                map[i][j] = str.charAt(j);
            }
        } //배열 입력 (빈칸은 0, 미네랄은 -1로 표시)
        


        N = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++) {
            int height = Integer.parseInt(st.nextToken()); //현재 던질 높이

            deleteMineral(R-height,i%2); //미네랄 지워주기
            setCluster();
        }//높이 저장

        printMap();
    }

    private static void setCluster() {
        //클러스터 찾기
        cluster = new int[R][C];
        int cnt = 1;

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(map[i][j] == 'x' && cluster[i][j] == 0){
                    if(findCluster(i,j,cnt)) return;
                }
                cnt++;
            }
        }
    }

    private static boolean findCluster(int row, int col, int cnt) {

        int low_height = Integer.MIN_VALUE;

        Queue<Node> queue = new LinkedList<>();
        ArrayList<Node> list = new ArrayList<>();

        queue.add(new Node(row,col));
        cluster[row][col] = cnt;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            low_height = Math.max(low_height, node.x); //제일 땅과 가까운 높이 구하기

            for(int d=0;d<4;d++){
                int nx = node.x + dx[d];
                int ny = node.y + dy[d];

                if(nx<0 || ny<0 || nx>=R || ny>=C) continue; //범위 벗어날 시 ㅌㅌ

                if(cluster[nx][ny] == 0 && map[nx][ny] == 'x'){
                    cluster[nx][ny] = cnt;
                    queue.add(new Node(nx,ny));
                }//사방향 탐색 시 미네랄 발견 시 클러스터 배열에 현재 cnt값 넣어주고 queue에도 넣어주기기
            }
            
            list.add(node); // 4방향 다 클러스터면 리스트에 넣어주기
        }
        
        if(low_height != R-1){
            downMap(list);
            return true;
        }// 클러스터가 공중에 떠 있으면 내려주기
        
        return false;
    }


    private static void printMap(){
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    private static void downMap(ArrayList<Node> list) {
        int down = 1;

        for(Node node : list) map[node.x][node.y] = '.'; // 현재 클러스터 위치 일단 비워두기

        outerLoop:
        while(true){
            for(Node node : list){
                //밑으로 한 칸 내렸을 때 범위 벗어나거나
                //한 칸 내렸을 시 다른 클러스터 || 미네랄 만나면 그만 내려가야함
                if(node.x + down == R || map[node.x+down][node.y] =='x'){
                    down--;
                    break outerLoop;
                }
            }
            
            down++; //계속 내려갈 수 있음
        }
        
        for(Node node : list){
            map[node.x+down][node.y] = 'x';
        } // 내려주기

    }


    private static void deleteMineral(int height, int side) {
        //side ==0 왼쪽부터 시작
        //side ==1 오른쪽부터 시작
        
        if(side == 0){ //왼쪽부터 시작
            for(int i=0;i<C;i++){
                if(map[height][i] =='x'){
                    map[height][i] = '.';
                    return;
                }// 배열 중 미네랄 발견 시 미네랄 지워주고 break
            } 
        }
        
        else{ //오른쪽부터 시작
            for(int i=C-1;i>=0;i--){
                if(map[height][i] =='x'){
                    map[height][i] = '.';
                    return;
                }//배열 중 미네랄 발견 시 미네랄 지워주고 break
            }
        }
        
    }



    static class Node{
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

클러스터를 어떻게 인식해야 하는가에 대해 고민이 많았다.

 

[참고한 블로그] (https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-2933-%EB%AF%B8%EB%84%A4%EB%9E%84-JAVA%EC%9E%90%EB%B0%94)