BOJ 2933 - 미네랄

2933번: 미네랄

 

동굴 내에서 막대 던지기를 한다. 막대는 미네랄을 파괴할 수도 있다.

R행 C열의 동굴. 각 칸은 빈칸 혹은 미네랄. 네 방향 중 하나로 인접한 미네랄 = 같은 클러스터

번갈아가며 막대를 던진다. 막대를 던지기 전에 던질 높이를 정한다. 막대는 땅과 수평을 이루며 날아간다.

날아가는 도중에 미네랄을 만나면 그 칸의 미네랄은 모두 파괴되며 막대는 그 자리에서 멈춘다.

클러스터라는 개념이 등장한다. 미네랄이 파괴된 이후 남은 클러스터가 분리될 수 있다고 하는데 이 부분부터 이해가 필요하다.

지도가 2차원 평면을 나타내는 것이 아니라 세로가 높이를 나타내고 있다.

막대를 던지는 높이는 1 ~ R 사이로 주어지며 이를 통해서 미네랄이 상하로 갈라지는 것이다.

필요한 기능

1. 턴을 구분한다.→ height를 순회하면서 %2 == 0 이면 left → right이다.
2. 막대를 던지는 기능 → height가 r이 돼서 거기부터 c를 증가시켜 가며 처음 미네랄을 만나는 곳을 찾는다.
3. 미네랄 클러스터 판단 클러스터를 확인할 수 있어야 한다. 클러스터가 하강하는 경우 = 바닥과 연결이 안 돼 있다.
   1. 미네랄과 충돌할 시 해당 위치의 4방향 기준 시작점으로 추가한 뒤 탐색을 시작
   2. 탐색 중 바닥과 연결되지 않은 것이 하강하는 클러스터
4. 하강할 클러스터를 어떻게 하강시키는가? 떨어지는 동안 클러스터의 모양이 유지된다.
   1. 떨어지다가 바닥에 도달하지 않았는데 다른 미네랄에 걸리는 경우
   2. 걸리지 않고 가장 아래 부분이 바닥에 도달하는 경우

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2933 {

    static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //상하좌우
    static FastReader scan = new FastReader();
    static int R, C, N;
    static char[][] initialMap;
    static int[] heights;

    static class Result {
        boolean isDown;
        List<int[]> cand;

        public Result(boolean isDown, List<int[]> cand) {
            this.isDown = isDown;
            this.cand = cand;
        }
    }

    static void input() {
        R = scan.nextInt();
        C = scan.nextInt();
        initialMap = new char[R][C];
        for (int i = 0; i < R; i++) {
            initialMap[i] = scan.next().toCharArray();
        }
        N = scan.nextInt();
        heights = new int[N];
        for (int i = 0; i < N; i++) {
            heights[i] = R - scan.nextInt(); // 높이
        }
    }

    static void print(char[][] map) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < map.length; i++) {
            sb.append(map[i]);
            if (i != map.length -1) {
                sb.append("\\n");
            }
        }
        System.out.println(sb);
    }

    static void solve(char[][] map) {
        for (int i = 0; i < N; i++) {
            int height = heights[i];
            int[] target;
            if (i % 2 == 0) {
                target = findMineral(map, height, 0);
            } else {
                // right to left
                target = findMineral(map, height, 1);
            }
            if (target == null) {
                continue; // 맞은 미네랄이 없다.
            }

            map[target[0]][target[1]] = '.';

            // 해당 타겟 기중 상하좌우를 보고 하강 클러스터 후보 찾기
            List<int[]> cand = new ArrayList<>();
            for (int d = 0; d < 4; d++) {
                int nr = target[0] + DIRECTION[d][0];
                int nc = target[1] + DIRECTION[d][1];
                if (!inRange(nr, nc)) {
                    continue;
                }
                if (map[nr][nc] == 'x') {
                    cand.add(new int[]{nr, nc});
                }
            }

            if (cand.isEmpty()) {
                // 상하좌우에 연결된 미네랄이 없다 -> 클러스터 후보가 없다.
                continue;
            }

            List<List<int[]>> clusters = new ArrayList<>();
            boolean[][] visited = new boolean[R][C];

            for (int[] mineral : cand) {
                if (!visited[mineral[0]][mineral[1]]) {
                    Result result = findDownCluster(map, mineral);
                    if (result.isDown) {
                        clusters.add(result.cand);
                    }
                    for (int[] pos : result.cand) {
                        visited[pos[0]][pos[1]] = true;
                    }
                }
            }

            for (List<int[]> cluster : clusters) {
                for (int[] pos : cluster) {
                    map[pos[0]][pos[1]] = '.';
                }

                int minHeight = calcDownHeight(cluster, map);

                for (int[] pos : cluster) {
                    map[pos[0] + minHeight][pos[1]] = 'x';
                }
            }
        }
        print(map);
    }

    static int calcDownHeight(List<int[]> cluster, char[][] map) {
        int minHeight = Integer.MAX_VALUE;
        for (int[] pos : cluster) {
            int r = pos[0];
            int c = pos[1];
            int h = 0;
            r++;
            while (inRange(r, c) && map[r][c] != 'x') {
                h++;
                r++;
            }
            minHeight = Math.min(minHeight, h);
        }
        return minHeight;
    }

    static Result findDownCluster(char[][] map, int[] start) {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[R][C];
        q.add(start);
        visited[start[0]][start[1]] = true;
        List<int[]> cand = new ArrayList<>();
        boolean isBottom = false;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            cand.add(curr);
            int r = curr[0];
            int c = curr[1];
            if (r == R - 1) {
                // 밑바닥 도달
                isBottom = true;
            }

            for (int d = 0; d < 4; d++) {
                int nr = r + DIRECTION[d][0];
                int nc = c + DIRECTION[d][1];

                if (!inRange(nr, nc)) continue;
                if (visited[nr][nc]) continue;
                if (map[nr][nc] == 'x') {
                    q.add(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }
        }
        return isBottom ? new Result(false, List.of()) : new Result(true, cand);
    }

    static boolean inRange(int r, int c) {
        return r >= 0 && r < R && c >= 0 && c < C;
    }

    static int[] findMineral(char[][] map, int r, int dir) {
        if (dir == 0) {
            // left to right
            for (int i = 0; i < C; i++) {
                if (map[r][i] == 'x') {
                    return new int[]{r, i};
                }
            }
        } else {
            for (int i = C - 1; i >= 0; i--) {
                if (map[r][i] == 'x') {
                    return new int[]{r, i};
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        input();
        solve(copy(initialMap));
    }

    private static char[][] copy(char[][] initialMap) {
        return Arrays.stream(initialMap)
                .map(char[]::clone)
                .toArray(char[][]::new);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}