[JAVA] BOJ 백준 2933번 - 미네랄

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2933번: 미네랄

---

2. 내가 푼 방법

구현이 필요한 BFS 문제이다. 클러스터를 찾을 때 BFS 알고리즘이 필요로 하고, 나머지는 실수 없이 구현해가면 된다.

 

나는 크게 막대기를 던져 미네랄을 파괴하는 함수, 인접한 클러스터를 찾는 함수, 클러스터가 중력을 받는 함수로 기능을 분리했다. 우선 문제에서는 바닥이 1로 시작되기 때문에, 던지는 높이를 받을 때 위쪽이 1로 시작될 수 있도록 조정했다.

for (int i = 0; i < N; i++) {
    attacks[i] = R - Integer.parseInt(st.nextToken()) + 1;
}

 

막대기를 던지는 순서는 왼쪽, 오른쪽 번갈아가기 때문에 막대기를 던지는 높이와 공격 방향을 같이 인자로 넘겨주었다. 공격 방향에 따라 막대기의 열을 이동시켰고, 인덱스 범위를 벗어난다면 파괴할 미네랄이 존재하지 않다는 의미이므로 바로 다음 공격을 할 수 있도록 리턴해주었다.

public static void solution() {
    for (int i = 0; i < attacks.length; i++) {
        if (i % 2 == 0) {
            attack(attacks[i], 1, 0);
        }
        else {
            attack(attacks[i], C, 1);
        }
    }
}

public static void attack(int x, int y, int d) {
    while(arr[x][y] != 'x') {
        y += dAttack[d];

        if (y == 0 || y > C) return;
    }

    // 미네랄 파괴
    arr[x][y] = '.';

    // 클러스터 확인
    checkCluster(x, y);
}

 

만약 미네랄이 파괴되었다면, 주변 클러스터를 확인해야 한다. 따라서 파괴된 미네랄의 상하좌우를 기준으로 findCluster 함수에서 관련 클러스터를 찾아주었다. 찾은 클러스터들은 moveDown 함수를 통해 공중에 떠있을 경우에 아래로 떨어질 수 있도록 했다. 이때 문제에서 2개 이상의 클러스터가 떨어지는 경우가 없다고 하니 바로 break; 문을 통해 빠져나온다. 

private static void checkCluster(int x, int y) {

    for (int i = 0; i < dx.length; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx == 0 || ny == 0 || nx > R || ny > C) continue;
        if (arr[nx][ny] == '.') continue;

        if (moveDown(findCluster(nx, ny))) break;
    }
}

public static List<Tuple> findCluster(int i, int j) {
    List<Tuple> result = new ArrayList<>();
    Queue<Tuple> queue = new ArrayDeque<>();
    boolean[][] visit = new boolean[R+1][C+1];

    queue.add(new Tuple(i, j));
    visit[i][j] = true;

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

        result.add(new Tuple(x, y));

        for (int d = 0; d < dx.length; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx == 0 || ny == 0 || nx > R || ny > C) continue;
            if (arr[nx][ny] == '.' || visit[nx][ny]) continue;

            visit[nx][ny] = true;
            queue.add(new Tuple(nx, ny));
        }
    }

    return result;
}

 

바닥으로 떨어져야 하는 미네랄일 경우를 canMoveDown 함수를 통해 확인하는데, 클러스터를 열(y)를 기준으로 행(x)을 제일 큰 값부터 정렬한다. 그래야 제일 바닥에 있는 칸을 확인할 수 있기 때문이다. 모든 열(y)의 제일 큰 행(x)을 확인하면서 하나라도 바닥과 맞닿아있다면 이동할 수 없도록 false를 리턴해주면 된다.

public static boolean moveDown(List<Tuple> clustering) {
    boolean move = false;
    while (canMoveDown(clustering)) {
        List<Tuple> tmp = new ArrayList<>();

        for (Tuple cluster : clustering) {
            tmp.add(new Tuple(cluster.x+1, cluster.y));
            arr[cluster.x+1][cluster.y] = arr[cluster.x][cluster.y];
            arr[cluster.x][cluster.y] = '.';
        }

        clustering = tmp;
        move = true;
    }
    return move;
}

public static boolean canMoveDown(List<Tuple> clustering) {
    // y를 기준으로 x 내림차순 정렬
    Collections.sort(clustering, new Comparator<Tuple>() {
        @Override
        public int compare(Tuple o1, Tuple o2) {
            if (o1.y == o2.y) return o2.x - o1.x;
            return o2.y - o1.y;
        }
    });

    int beforeY = -1;
    // 아래가 바닥이면 움직이지 못함
    for (Tuple cluster : clustering) {
        if (beforeY == cluster.y) continue;

        // 최초의 x행
        beforeY = cluster.y;

        if (cluster.x == R || arr[cluster.x + 1][cluster.y] == 'x') return false;
    }

    return true;
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2933.java

import java.sql.Array;
import java.util.*;
import java.io.*;

class Main {
    static int R, C;
    static char[][] arr;
    static int[] attacks;
    static int[] dAttack = {1, -1};
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};

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

    public static void solution() {
        for (int i = 0; i < attacks.length; i++) {
            if (i % 2 == 0) {
                attack(attacks[i], 1, 0);
            }
            else {
                attack(attacks[i], C, 1);
            }
        }
    }

    public static void attack(int x, int y, int d) {
        while(arr[x][y] != 'x') {
            y += dAttack[d];

            if (y == 0 || y > C) return;
        }

        // 미네랄 파괴
        arr[x][y] = '.';

        // 클러스터 확인
        checkCluster(x, y);
    }

    private static void checkCluster(int x, int y) {

        for (int i = 0; i < dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx == 0 || ny == 0 || nx > R || ny > C) continue;
            if (arr[nx][ny] == '.') continue;

            if (moveDown(findCluster(nx, ny))) break;
        }
    }

    public static List<Tuple> findCluster(int i, int j) {
        List<Tuple> result = new ArrayList<>();
        Queue<Tuple> queue = new ArrayDeque<>();
        boolean[][] visit = new boolean[R+1][C+1];

        queue.add(new Tuple(i, j));
        visit[i][j] = true;

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

            result.add(new Tuple(x, y));

            for (int d = 0; d < dx.length; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx == 0 || ny == 0 || nx > R || ny > C) continue;
                if (arr[nx][ny] == '.' || visit[nx][ny]) continue;

                visit[nx][ny] = true;
                queue.add(new Tuple(nx, ny));
            }
        }

        return result;
    }

    public static boolean moveDown(List<Tuple> clustering) {
        boolean move = false;
        while (canMoveDown(clustering)) {
            List<Tuple> tmp = new ArrayList<>();

            for (Tuple cluster : clustering) {
                tmp.add(new Tuple(cluster.x+1, cluster.y));
                arr[cluster.x+1][cluster.y] = arr[cluster.x][cluster.y];
                arr[cluster.x][cluster.y] = '.';
            }

            clustering = tmp;
            move = true;
        }
        return move;
    }

    public static boolean canMoveDown(List<Tuple> clustering) {
        // y를 기준으로 x 내림차순 정렬
        Collections.sort(clustering, new Comparator<Tuple>() {
            @Override
            public int compare(Tuple o1, Tuple o2) {
                if (o1.y == o2.y) return o2.x - o1.x;
                return o2.y - o1.y;
            }
        });

        int beforeY = -1;
        // 아래가 바닥이면 움직이지 못함
        for (Tuple cluster : clustering) {
            if (beforeY == cluster.y) continue;

            // 최초의 x행
            beforeY = cluster.y;

            if (cluster.x == R || arr[cluster.x + 1][cluster.y] == 'x') return false;
        }

        return true;
    }

    public static class Tuple implements Comparable<Tuple> {
        int x;
        int y;

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

        @Override
        public int compareTo(Tuple t) {
            return t.x - this.x;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                bw.write(arr[i][j]);
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }

    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());
        arr = new char[R+1][C+1];

        for (int i = 1; i <= R; i++) {
            String line = br.readLine();
            for (int j = 1; j <= C; j++) {
                arr[i][j] = line.charAt(j - 1);
            }
        }

        int N = Integer.parseInt(br.readLine());
        attacks = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            attacks[i] = R - Integer.parseInt(st.nextToken()) + 1;
        }

        br.close();
    }
}

---

4. 결과 및 회고

사실 이번 처음 봤을 때 문제를 실수 없이 풀어야겠다고 스스로 다짐했다. 근데,, 바르게 구현을 다 해두고 출력할 때 공백을 포함시켜서 삽질하고 나니 어이가 없넹 ㅎㅅㅎ,,