[백준 2933] 미네랄 -JAVA //le_effort

미네랄

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	4995	1266	806	23.451%

문제

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

출력

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

예제 입력 1 복사

xxxxxxxxxx
8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1

예제 출력 1 복사

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

 

풀이

문제 이해하는 것도 너무 어렵다...

구현도 자잘한 것도 신경 써줘야 하고 힘든 문제였다

 

문제에서 가장 이해가 안됐던게 클러스터에 대한 이해였다.

 

우선 풀이를 말하면

왼쪽/오른쪽 막대기 던지는걸 구분해주고

막대기가 격파한 미네랄 (1개)를 맵에서 "." 로 표현해주고

bfs를 돌린다.

 

bfs를 돌릴 때는 가장 밑 부분에서 부터 미네랄을 넣는다

즉 무슨 말이냐면 문제에서 공중에 떠 있는 미네랄 클러스터는 없다 라고 표시 돼 있다.

그럼 막대기가 격파하고 분리된 클러스터를 구하려면

막대기가 부셔지고 나서 공중에 떠 있는 클러스터를 구하면 된다.

 

이 문제에서 클러스터는 무조건 1개 나온다.

문제에서 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.

라는 표현이 있는데 이 말은 문제의 테스트케이스에서 주어지는 입력은

막대기가 격파하면 클러스터가 1개만 나온다는 뜻이니까

 

실제로 문제 풀이 할 땐 며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 이 부분을 고려하지 않아도 된다.

 

다시 bfs얘기로 돌아와서

bfs는 맵의 제일 아래부분에서 미네랄 인 부분을 찾고 큐에 넣어준다

그 다음에 여지껏 하던것 처럼 bfs를 하면

"공중에 떠 있지않은" 미네랄 들을 얻을 수 있다

왜 ? 공중에 떠 있지 않도록 행렬의 가장 바닥의 미네랄들을 담아주고

bfs를 탐색했으니 bfs를 통해 탐색 되는 부분은 땅에 연결된 것이고

bfs 를 통해 탐색이 되지 않는 부분은 공중에 떠 있는 클러스터 인 것이다.

 

위의 그림에서 O가 미네랄, ㅁ 이 빈칸이라 했을때

첫번째 클러스터가 떨어지면 아래의 그림 처럼 된다.

문제의 조건 중 클러스터는 떨어 질 때 모양을 유지하면서 떨어진다 라고 명시 돼 있다.

 

즉 그럼 bfs를 통해 땅 과 연결된 미네랄 들을 얻고 (visited = true)

전체 맵을 탐색하면서 해당 좌표가 미네랄이며,visited = false 인 부분들은

공중에 떠 있는 클러스터들 이다.

 

이제 이 클러스터들을 떨어트릴때 위의 사진처럼 모양을 유지하면서 떨어지려면

공중에 떠 있는 클러스터들 중 한 개의 미네랄의 다음칸이 미네랄 이거나

맵의 바닥 까지 가는 경우 까지

x인덱스를 더해주면서 확인 하면 된다

 

아래 코드에 주석도 달아 놓았다.

전체코드

x
import java.io.*;
import java.util.*;
public class Main {
    static int r,c,n;
    static String map[][];
    static boolean visited[][];
    static int[] arr;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static int debug = 1;
    static ArrayList<Node>list = new ArrayList<>(); // 클러스터 들을 담을 것
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        
        r = Integer.parseInt(t[0]);
        c = Integer.parseInt(t[1]);
        
        map = new String[r+1][c+1];
        
        for(int i=1; i<=r; i++) {
            String[] map_input = br.readLine().split("");
            for(int j=1; j<=c; j++) {
                map[i][j] = map_input[j-1];
            }
        }
        
        n = Integer.parseInt(br.readLine());
        arr = new int[n+1]; // 막대를 던진 높이저장
        
        String[] tt = br.readLine().split(" "); // 막대를 던진 높이
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(tt[i]);
        }
        
        for(int i=0; i<n; i++) {    // n개의 막대를 던져본다
            int num = r-arr[i]+1;   // 문제중 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다를 바꿔주기 
            
            if(i%2==0) {        // 왼쪽에서 막대를 던질때
                solve(num,true);
            }
            else {  //오른쪽에서 막대를 던질때
                solve(num,false);
            }
        }
        for(int i=1; i<=r; i++) {
            for(int j=1; j<=c; j++) {
                System.out.print(map[i][j]+"");
            }
            System.out.println();
        }
        
    }
    public static void solve(int num, boolean flag) {
        visited = new boolean[r+1][c+1];
        if(flag) {  // 왼쪽에서 막대 던질때
            for(int i=1; i<=c; i++) {
                if(map[num][i].equals("x")) {
                    map[num][i] = ".";      // 막대를 던져 미네랄을 부심
                    //bfs();
                    // 위에 bfs() 주석이 있는 이유는 내가 실제로 이렇게 했다가 틀려서 냅뒀다.
                    // 막대기를 던질 때 막대기를 던지는 해당 열에 무조건 하나 이상의 미네랄이 있다고 가정하고 했었는데
                    // 주어지는 입력중엔 막대기를 던지는 열에 미네랄이 없는 경우도 있어서 bfs가 실행 되지 않았다.
                    break;
                }
            }
            bfs();
        }
        else {  // 오른쪽에서 막대 던질때
            for(int i=c; i>=1; i--) {
                if(map[num][i].equals("x")) {
                    map[num][i] =".";
                    //bfs();
                    break;
                }
            }
            bfs();
        }
        get_cluster();
        move();
    }
    public static void move() {
        int cnt =0;
        boolean flag= true;
        for(int i=0; i<list.size(); i++) {  //미리 맵을 초기화 해줘야한다
            Node a =list.get(i);
            map[a.x][a.y]= "."; 
        }
        
        while(true) {
            if(list.size() ==0) {   // 이 경우 클러스터가 없을 때 탈출을 못해서 무한루프를 방지하기 위함
                break;
            }
            cnt++;
            for(int i=0; i<list.size(); i++) {
                Node cluster = list.get(i);
                int x = cluster.x;
                int y = cluster.y;
                if(map[x+cnt][y].equals("x")) { // 다음칸이 미네랄이면
                    // 위에서 미리 맵을 초기화 해주지 않았으면 공중에 떠 있는 클러스터들도 포함된다.
                    // 우리의 목표는 공중에 떠 있는 클러스터가 아니라 땅과 연결 돼 있는 미네랄에 접근하는 것이다.
                    cnt--;
                    flag = false;
                    break;
                }
        
                if(x+cnt==r) {
                    flag = false;
                    break;
                }
            }
            if(!flag) {
                break;
            }
        }
        
        for(int i=0; i<list.size(); i++) {
            Node a = list.get(i);
            a.x+=cnt;
            map[a.x][a.y]="x";   // 내려간 위치에 미네랄로 바꿔줌
        }
    }
    public static void get_cluster() {
        list.clear();
        for(int i=1; i<=r; i++) {
            for(int j=1; j<=c; j++) {
                if(!visited[i][j] && map[i][j].equals("x")) {
                    list.add(new Node(i,j));
                }
            }
        }
    }
    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        for(int i=1; i<=c; i++) {   //제일 밑 바닥의 미네랄을 큐에 넣음
            if(map[r][i].equals("x")) {
                q.add(new Node(r,i));
                visited[r][i] = true;
            }
        }
​
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(isRange(nx,ny) && !visited[nx][ny] && map[nx][ny].equals("x")) {
                    q.add(new Node(nx,ny));
                    visited[nx][ny] = true;
                }
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=r && y<=c) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}