[백준] 2933. 미네랄

전형적인 시뮬레이션 문제. 조건을 잘 보고 구현하는 것이 중요하다.

 

2933번: 미네랄

 

풀이

처음에 문제 이해하는데도 시간이 걸렸다..

 

막대기를 던진다고 해서 포물선으로 날아가는 모습을 떠올렸으나 그렇진 않고 해당 높이에 레이저 포인터를 쏜다고 생각하면 된다.

 

막대기 높이와 실제 2차원 배열상의 인덱스는 반대이므로 먼저 계산해서 처리해주면 된다.

 

 

 

클러스터를 어떻게 내릴 것인지 고민을 좀 했다..

 

 

우선 클러스터가 되는 모든 미네랄 좌표를 ArrayList (mineral)에 넣어 저장하고

Comparator를 override하여 열 기준으로 내림차순이 되도록 정렬했다.

 

그리고 가장 밑부분들의 좌표를 따로 모아 ArrayList (bottom)에 저장하고

이 좌표들에 대해 밑으로 얼마나 내려갈 수 있는지 계산했고 (cnt에 저장)

최종적으로 갈 수 있는 칸만큼 한번에 클러스터를 내리는 방법을 사용했다.

 

 

 

 

 

 

 

테스트 케이스가 하나밖에 없어서 검증하기 어려우니 질문게시판에 있는 반례 몇 개를 넣어 테스트 해볼 것을 추천한다.

 

글 읽기 - [2933] 미네랄 반례 모음

 

Logic

1. (막대기 순서)%2 값에 따라 왼쪽, 오른쪽에서 던지는 경우를 구별한다.
2. 막대기를 던지다가 미네랄에 맞았으면 .으로 치환하고 부신 미네랄 기준으로 네 방향 BFS 탐색을 한다.
   • BFS탐색시 탐색하는 미네랄 좌표를 mineral에 저장한다.
   • 클러스터일 경우 mineral좌표를 정렬하고 클러스터의 가장 아래 좌표를 구한다.
   • 클러스터가 최대 몇 칸만큼 내려갈 수 있는지 구하고 해당 칸만큼 클러스터를 내린다.
3. 마지막에 map을 출력한다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    static int R, C, N;
    static List<Mineral> mineral;
    static char[][] map;
    static boolean[][] visited;
    static int[] order;
    static int[] pos_r = { 1, 0, -1, 0 };
    static int[] pos_c = { 0, 1, 0, -1 };

    public static void main(String[] args) throws IOException {
        input();
        solve();
        print();
    }

    public static void print() {
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                System.out.print(map[r][c]);
            }
            System.out.println();
        }
    }

    public static void input() 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 r = 0; r < R; r++) {
            char[] temp = br.readLine().toCharArray();

            for (int c = 0; c < C; c++)
                map[r][c] = temp[c];
        }

        N = Integer.parseInt(br.readLine());
        order = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++)
            order[n] = Integer.parseInt(st.nextToken());
    }

    public static void solve() {
        for (int n = 0; n < N; n++) {
            int bar = R - order[n];

            if ((n + 2) % 2 == 0) {
                loop:
                    for (int c = 0; c < C; c++) {
                        int r = bar;
                        if (map[r][c] == 'x') {
                            map[r][c] = '.';
                            for (int d = 0; d < 4; d++) {
                                int nr = r + pos_r[d];
                                int nc = c + pos_c[d];

                                if (nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc] != 'x') continue;

                                mineral = new ArrayList<>();
                                if (BFS(nr, nc)) moveCluster(nr, nc);
                            }
                            break loop;
                        }
                    }
            }
            else {
                loop:
                    for (int c = C - 1; c >= 0; c--) {
                        int r = bar;
                        if (map[r][c] == 'x') {
                            map[r][c] = '.';
                            for (int d = 0; d < 4; d++) {
                                int nr = r + pos_r[d];
                                int nc = c + pos_c[d];

                                if (nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc] != 'x') continue;

                                mineral = new ArrayList<>();
                                if (BFS(nr, nc)) moveCluster(nr, nc);
                            }
                            break loop;
                        }
                    }
            }
        }
    }

    public static boolean BFS(int r, int c) {
        visited = new boolean[R][C];
        boolean cluster = true;
        Queue<Mineral> q = new LinkedList<>();
        mineral.add(new Mineral(r, c));
        q.offer(new Mineral(r, c));
        visited[r][c] = true;

        while(!q.isEmpty()) {
            int x = q.peek().x;
            int y = q.peek().y;
            q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = x + pos_r[d];
                int nc = y + pos_c[d];

                if (nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc] != 'x' || visited[nr][nc]) continue;
                if (nr == R - 1) cluster = false;

                visited[nr][nc] = true;
                q.offer(new Mineral(nr, nc));
                mineral.add(new Mineral(nr, nc));
            }
        }

        return cluster;
    }

    public static void moveCluster(int r, int c) {
        Collections.sort(mineral, new Comparator<Mineral>() {

            @Override
            public int compare(Mineral o1, Mineral o2) {
                if (o1.y == o2.y)
                    return Integer.compare(o1.x, o2.x) * (-1);
                return Integer.compare(o1.y, o2.y);
            }

        });

        // 클러스터 밑부분 정보 뽑기
        List<Mineral> bottom = new ArrayList<>();
        bottom.add(new Mineral(mineral.get(0).x, mineral.get(0).y));

        int temp = mineral.get(0).y;
        for (int i = 0; i < mineral.size(); i++) {
            if (mineral.get(i).y > temp) {
                temp++;
                bottom.add(new Mineral(mineral.get(i).x, mineral.get(i).y));
            }
        }

        // bottom 정보로 얼마나 내려갈 수 있는지 보기
        int cnt = 0;
        for (int i = 1; i < R; i++) {
            boolean flag = true;
            for (int b = 0; b < bottom.size(); b++) {
                int x = bottom.get(b).x;
                int y = bottom.get(b).y;
                if (x + i >= R || map[x + i][y] == 'x') flag = false;
            }
            if (!flag) break; 
            cnt++;
        }

        // 내려갈 수 있는 칸만큼 한방에 내리기
        for (int i = 0; i < mineral.size(); i++) {
            int x = mineral.get(i).x;
            int y = mineral.get(i).y;

            map[x][y] = '.';
            map[x + cnt][y] = 'x';
        }
    }

    static class Mineral {
        int x;
        int y;

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

 

실행 결과