문제

창영 vs 상근.. in 동굴..

막대는 일정한 높이에서 날아가고, 각 턴마다 던지는 방향이 바뀐다. 
막대가 미네랄을 만나면 그 미네랄은 없어지게되고, 없어진 후 남은 클러스터 덩어리가 아래로 내려와야한다.
남은 클러스터의 덩어리가 1개보다 많은 경우는 없다. 아래로 내려오면서 모양은 변하지 않는다.

풀이

1. 맵을 입력받고, 던지는 횟수만큼 막대를 던지고 (throwStrick), 아래로 내리기 (down)를 반복한다.
   이때 idx로 방향을 구분한다.
2. throwStick()

• 인자로 높이와 idx(던지는 방향)을 받는다.
• idx가 1이면 -> 방향으로, -1이면 <- 방향으로 for문을 돌면서 미네랄을 만나면 없애준다.
• 한 칸의 미네랄만 없애야 하기 때문에 하나라도 파괴했으면 바로 break

3. down()
   바닥에 있는 클러스터를 조사하고, 그를 제외한 클러스터가 더 존재하면 아래로 내린다.

• bsf로 구현했다.
• 이중 포문을 순회하면서 바닥에 있는 클러스터를 제외한 클러스터가 존재하면 ArrayList에 넣어준다.
• ArrayList에는 맨 위부터의 미네랄의 좌표들이 들어가있다.

        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                if (!visited[i][j] && map[i][j] == 'x') {
                    cluster.add(new Point(i, j));
                    map[i][j] = '.';
                }
            }
        }

맨 위부터 하나씩 검사하면서 내려주는 방식으로 했다. 맨 아래쪽부터 검사하면 모양을 유지한 채로 내려올 수 없다.

• ArrayList에 들어있는 클러스터중 하나라도 아래로 내려갈 수 없다면 못 떨어진다. --> flag로 체크한다.

소스 코드

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

public class BOJ_2933 {
    static char[][] map;
    static boolean[][] visited;
    static Queue<Point> q = new LinkedList<>();
    static int r;
    static int c;
    static int n; // 던지는 횟수
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        map = new char[r + 1][c + 1];

        for (int i = 1; i <= r; i++) {
            String[] input = br.readLine().split("");
            for (int j = 1; j <= c; j++) {
                map[i][j] = input[j - 1].charAt(0);
            }
        }

        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int idx = 1; // 1이면 왼->오, -1이면 오->왼
        for (int i = 1; i <= n; i++) {
            throwStick(r - Integer.parseInt(st.nextToken()) + 1, idx);
            down();

            idx *= -1;
        }

        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                bw.write(map[i][j]);
            }
            bw.newLine();
        }
        bw.flush();
    }

    static void throwStick(int h, int idx) {
        int start;
        int temp;

        if (idx > 0) {
            start = 1;
        } else {
            start = c;
        }

        temp = start;
        for (int i = 1; i <= c; i++) {
            if (map[h][temp] == 'x') {
                map[h][temp] = '.';
                break;
            }

            temp += idx;
        }
    }

    static void down() {
        visited = new boolean[r + 1][c + 1];
        ArrayList<Point> cluster = new ArrayList<>();

        /* 바닥에 있는 클러스터 체크 */
        for (int i = 1; i <= c; i++) {
            if (map[r][i] == '.' || visited[r][i]) {
                continue;
            }

            q.add(new Point(r, i));
            visited[r][i] = true;

            while (!q.isEmpty()) {
                Point p = q.poll();

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

                    if (nx >= 1 && ny >= 1 && nx <= r && ny <= c) {
                        if (map[nx][ny] == 'x' && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.add(new Point(nx, ny));
                        }
                    }
                }
            }
        }

        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                if (!visited[i][j] && map[i][j] == 'x') {
                    cluster.add(new Point(i, j));
                    map[i][j] = '.';
                }
            }
        }

        if (cluster.isEmpty()) {
            return;
        }

        boolean flag = true;
        while (flag) {
            for (Point p : cluster) {
                int x = p.x + 1;
                int y = p.y;

                /* 아래로 내려갈 수 없는 경우 flag = false */
                if (x < 1 || y < 1 || x > r || y > c || map[x][y] == 'x') {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                for (Point p : cluster) {
                    p.x++;
                }
            }
        }

        for (Point p : cluster) {
            map[p.x][p.y] = 'x';
        }
    }

    static class Point {
        int x;
        int y;

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

헤맨 부분

클러스터를 아래로 내려야할 때, 아래가 미네랄인 경우만 내릴 수 없다고 생각해서

if(x < 1 || y < 1 || x > r || y > c) continue;

if (map[x][y] == 'x') {
	flag = false;
    break;
}

이런 식으로 처리했었다.
그런데 생각해보니 좌표를 벗어나는 경우도 함께 내릴 수 없는 걸로 처리해줘야 하기 때문에!!!!