[백준]2933: 미네랄(java)

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

2933번: 미네랄

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력 1 

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

예제 출력 1 

......
......
..xx..
..xx..
.xxxx.

---

풀이

시뮬레이션 문제였다. 단계별로 풀이하겠습니다.

1.T회 던지는데 t%2가 짝수일땐 왼쪽, 홀수일땐 오른쪽에서 던져줍니다.

if(t%2==0) {
    throwStick(N-r, true);
} else {
    throwStick(N-r, false);
}

1-1) 던지는 로직은 다음과 같습니다.

public static void throwStick(int row, boolean isLeft) {
    if(isLeft) {
        for(int i=0; i<M; i++) {
            if(map[row][i] == 'x') {
                map[row][i] = '.';
                return;
            }
        }
    } else {
        for(int i=M-1; i>=0; i--) {
            if(map[row][i] == 'x') {
                map[row][i] = '.';
                return;
            }
        }
    }
}

왼쪽에서 던지면 0부터 던지고 오른쪽에서 던지면 M-1부터 던져줍니다.

2. 던진 후 클러스터가 분리된 것이 있는지 확인합니다.

boolean[][] visited = new boolean[N][M];
loop: for(int i=0; i<N; i++) {
    for(int j=0; j<M; j++) {
        if(map[i][j] == 'x') {
            if(visited[i][j]) continue;
            mineral = new HashSet<>();
            visited[i][j] = true;
            if(!isClusterWithBottom(i, j, visited)) {
                moveCluster();
                break loop;
            }
        }
    }
}

2-1) 클루스터가있다면 isClusterWithBottom함수를 통해 현재 이 클루스터가 바닥과 연결돼있는지 확인합니다.

public static boolean isClusterWithBottom(int r, int c, boolean[][] visited) {
    Queue<Point> q = new LinkedList<>();
    int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean isTrue = false;
    q.add(new Point(r, c));
    mineral.add(new Point(r, c));
    while(!q.isEmpty()) {
        Point now = q.poll();
        if(now.x == N-1) {
            isTrue = true;
        }

        for(int i=0; i<4; i++) {
            int nx = now.x + dist[i][0];
            int ny = now.y + dist[i][1];

            if(!isIn(nx, ny) || visited[nx][ny] || map[nx][ny] != 'x') continue;
            visited[nx][ny] = true;
            mineral.add(new Point(nx, ny));
            q.add(new Point(nx, ny));
        }
    }
    if(isTrue) return true;
    else return false;
}

이 때 HashSet으로 이루어진 mineral을 체크합니다.

2-2) 클루스터가 바닥과 연결돼있지 않다면 아래로 내려줍니다.

public static void moveCluster() {
    int height = 100;
    Iterator<Point> iter = mineral.iterator();

    while(iter.hasNext()) {
        Point now = iter.next();
        int x = now.x;
        int y = now.y;
        map[x][y] = '.';
        for(int h=x+1; h<N; h++) {
            if(map[h][y] == 'x' && !mineral.contains(new Point(h, y))) {
                height = Math.min(height, h-x-1);
                break;
            }
        }
        height = Math.min(height, N-1-x);
    }

    Iterator<Point> iter2 = mineral.iterator();
    while(iter2.hasNext()) {
        Point now = iter2.next();
        int x = now.x;
        int y = now.y;
        map[x+height][y] = 'x';
    }
}

현재 클루트터를 iterator를 통해 돌면서 현재 클루스터와 바닥과의 높이차 최솟값을 갱신해줍니다.

후에 모든 클루스터들을 최솟값의 높이만큼 내려줍니다.

 

전체 코드

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

public class BJ_G2_2939_미네랄 {
    static class Point{
        int x;
        int y;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M;
    static char[][] map;
    static HashSet<Point> mineral;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder ans = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][];

        for(int i=0; i<N; i++) {
            map[i] = br.readLine().toCharArray();
        }
        int T = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int t=0; t<T; t++) {
            int r = Integer.parseInt(st.nextToken());
            if(t%2==0) {
                throwStick(N-r, true);
            } else {
                throwStick(N-r, false);
            }
            boolean[][] visited = new boolean[N][M];
            loop: for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(map[i][j] == 'x') {
                        if(visited[i][j]) continue;
                        mineral = new HashSet<>();
                        visited[i][j] = true;
                        if(!isClusterWithBottom(i, j, visited)) {
                            moveCluster();
                            break loop;
                        }
                    }
                }
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                ans.append(map[i][j]);
            }
            if(i!=N-1) ans.append("\n");
        }
        System.out.printf("%s", ans.toString());
    }

    public static void moveCluster() {
        int height = 100;
        Iterator<Point> iter = mineral.iterator();

        while(iter.hasNext()) {
            Point now = iter.next();
            int x = now.x;
            int y = now.y;
            map[x][y] = '.';
            for(int h=x+1; h<N; h++) {
                if(map[h][y] == 'x' && !mineral.contains(new Point(h, y))) {
                    height = Math.min(height, h-x-1);
                    break;
                }
            }
            height = Math.min(height, N-1-x);
        }

        Iterator<Point> iter2 = mineral.iterator();
        while(iter2.hasNext()) {
            Point now = iter2.next();
            int x = now.x;
            int y = now.y;
            map[x+height][y] = 'x';
        }
    }

    public static boolean isClusterWithBottom(int r, int c, boolean[][] visited) {
        Queue<Point> q = new LinkedList<>();
        int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean isTrue = false;
        q.add(new Point(r, c));
        mineral.add(new Point(r, c));
        while(!q.isEmpty()) {
            Point now = q.poll();
            if(now.x == N-1) {
                isTrue = true;
            }

            for(int i=0; i<4; i++) {
                int nx = now.x + dist[i][0];
                int ny = now.y + dist[i][1];

                if(!isIn(nx, ny) || visited[nx][ny] || map[nx][ny] != 'x') continue;
                visited[nx][ny] = true;
                mineral.add(new Point(nx, ny));
                q.add(new Point(nx, ny));
            }
        }
        if(isTrue) return true;
        else return false;
    }

    public static void throwStick(int row, boolean isLeft) {
        if(isLeft) {
            for(int i=0; i<M; i++) {
                if(map[row][i] == 'x') {
                    map[row][i] = '.';
                    return;
                }
            }
        } else {
            for(int i=M-1; i>=0; i--) {
                if(map[row][i] == 'x') {
                    map[row][i] = '.';
                    return;
                }
            }
        }
    }

    public static boolean isIn(int x, int y) {
        return 0<=x && x<N && 0<=y && y<M;
    }
}