백준 7569, 2573 - Java

백준 7569 토마토 

- 기존 BFS 방식에서 z축이 새로 생겼다고 보면 된다. 3차원 배열에 토마토 저장, 원래 BFS쓸 때 정의하는 x,y축 이동방향에 추가로 z축 이동방향(위 아래) 까지 정의해준다. 

- 남은 안익은 토마토 개수 left 정의해주기. 처음부터 left가 0일 수도 있다. bfs 들어가기전에 이거 먼저 걸러내기 

- 익은 토마토 위치들부터 큐에 넣어준다. 

- 따로 방문배열 만들지 않고 3차원 배열에 저장된 값이 0이면 아직 안 방문한 안익은 토마토라는 뜻이므로 이때만 큐에 넣어준다. 3차원 배열에 익은 시점을 저장하며 업데이트

- 큐를 다 돌았는데도 안 익은게 남았다면 -1, 다 익었다면 3차원 배열을 탐색하여 max값 찾은 후 -1을 해서 정답 출력. (1초부터 시작했기 때문에!)

 

import java.util.*;
import java.io.*;
public class p7569 {
    public static int[][][] graph; // 전체 토마토 개수 세서 하루 지날 때마다 다 익었나 비교
    public static int left = 0;
    public static int[] dirX = { 0, 0, 0, 0, 1, -1}; // 상하동서남북
    public static int[] dirY = { 0, 0, 1, -1, 0, 0};
    public static int[] dirZ = {-1, 1, 0, 0, 0, 0};

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

        int m = Integer.parseInt(st.nextToken()); // 가로
        int n = Integer.parseInt(st.nextToken()); // 세로
        int h = Integer.parseInt(st.nextToken()); // 층
        boolean isFin = false;

        graph = new int[n][m][h];
        Queue<Pos> queue = new LinkedList<>();
        for (int i = 0; i < h; i++) { // 층
            for (int j = 0; j < n; j++) { // 가로
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < m; k++) { // 세로
                    int temp = Integer.parseInt(st.nextToken());
                    if (temp == 0) {
                        // 익지 않은 토마토 개수 +1
                        left++;
                    }
                    else if (temp == 1) {
                        queue.add(new Pos(j, k, i));
                    }
                    graph[j][k][i] = temp;
                }
            }
        }

        if (left == 0) {
            System.out.println(0);
            return;
        }

        while (!queue.isEmpty()) {
            Pos poll = queue.poll();

            if (left == 0) {
                isFin = true;
                break;
            }

            for (int dir = 0; dir < 6; dir++) {
                int nextX = poll.x + dirX[dir];
                int nextY = poll.y + dirY[dir];
                int nextZ = poll.z + dirZ[dir];

                if (nextX < 0 || nextX >= n) {
                    continue;
                }
                if (nextY < 0 || nextY >= m) {
                    continue;
                }
                if (nextZ < 0 || nextZ >= h) {
                    continue;
                }
                if (graph[nextX][nextY][nextZ] == 0) {
                    queue.add(new Pos(nextX, nextY, nextZ));
                    graph[nextX][nextY][nextZ] = graph[poll.x][poll.y][poll.z] + 1;
                    left--;
                }

            }
        }
        if (!isFin) {
            System.out.println("-1");
        }
        else {
            int max = Integer.MIN_VALUE;
            for (int t = 0; t < h; t++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (graph[i][j][t] > max) {
                            max = graph[i][j][t];
                        }
                    }
                }
            }

            System.out.println(max - 1);
        }

    }

    static class Pos {
        int x;
        int y;
        int z;
        Pos (int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
}

 

---

백준 2573 빙산 

- 한덩어리가 두덩이가 되지 못한 채로 다 녹는 경우...를 고려해야한다. 이것때문에 헤맸는데 질문 게시판에서 해답을 찾음!!  아래 테스트 케이스 돌려서 제대로 0이 출력되나 확인할 것 

4 4

0 0 0 0

0 1 1 0

0 1 1 0

0 0 0 0

- 예전에 삼성 기출에서도 비슷한 유형을 봤던것 같은데, 얼음은 동시에 녹아야 한다. 하나 녹이고 다음칸 가서 녹이면 앞칸이 녹은것 때문에 다음 칸 녹을 양 계산할 때도 영향이 가기 때문이다. 미리 각 칸 별로 녹을 양을 저장해두고 한번에 녹이기! 

public static void meltIce() {
        ArrayList<Integer> melt = new ArrayList<>();

        for (Pos p : ice) {
            int meltAmount = 0;
            for (int i = 0; i < 4; i++) {
                if (map[p.x + dirX[i]][p.y + dirY[i]] == 0) {
                    meltAmount++;
                }
            }

            melt.add(meltAmount);
        } // 미리 녹일 양을 저장해둔다. 


        ArrayList<Pos> tempIce = new ArrayList<>(ice.size());
        tempIce.addAll(ice);

        for (int i = 0; i < melt.size(); i++) {
            Integer meltAmount = melt.get(i);
            Pos p = ice.get(i);
            if (meltAmount >= map[p.x][p.y]) {
                // 녹아야할 양이 더 많으면
                map[p.x][p.y] = 0;
                tempIce.set(i, new Pos(-1, -1));
            }
            else {
                // 기존 얼음 양만 감소
                map[p.x][p.y] -= meltAmount;
            }
        }

        ice = new ArrayList<>();

        for (Pos p : tempIce) {
            if (p.x != -1 && p.y != -1) {
                ice.add(p);
            }
        }

    }

- 참고로 위에서 Ice는 static 변수로, 얼음들의 위치를 저장해놓은 arraylist이다. 바로 ice에서 remove 하지 말고, tempIce에서 아직 얼음 남아있는 애들만 차례로 넣어주는 방식을 택했다. remove바로 해버리면 동시성 이슈 난다. 

 

전체 코드 

import java.io.*;
import java.util.*;
public class p2573 {
    static int[] dirX = { 0, 0, -1, 1}; // 동서남북
    static int[] dirY = { 1, -1, 0, 0};
    static int year = 0;
    static int x;
    static int y;
    static int[][] map;
    static boolean[][] visit;
    static ArrayList<Pos> ice;
    static boolean isDivided = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        ice = new ArrayList<>();
        map = new int[x][y];

        for (int i = 0; i < x; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < y; j++) {
                int temp = Integer.parseInt(st.nextToken());
                map[i][j] = temp;
                if (temp != 0) {
                    ice.add(new Pos(i, j));
                }
            }
        }

        while (ice.size() > 0 && !isDivided) {
            meltIce();
            year++;
            visit = new boolean[x][y];
            if (ice.size() == 0) {
                break;
            }
            BFS();
            for (Pos p : ice) {
                if (!visit[p.x][p.y]) {
                    isDivided = true;
                }
            }
        }

        if (isDivided) {
            System.out.println(year);
        } else {
            System.out.println(0);
        }

    }

    public static void meltIce() {
        ArrayList<Integer> melt = new ArrayList<>();

        for (Pos p : ice) {
            int meltAmount = 0;
            for (int i = 0; i < 4; i++) {
                if (map[p.x + dirX[i]][p.y + dirY[i]] == 0) {
                    meltAmount++;
                }
            }

            melt.add(meltAmount);
        }


        ArrayList<Pos> tempIce = new ArrayList<>(ice.size());
        tempIce.addAll(ice);

        for (int i = 0; i < melt.size(); i++) {
            Integer meltAmount = melt.get(i);
            Pos p = ice.get(i);
            if (meltAmount >= map[p.x][p.y]) {
                // 녹아야할 양이 더 많으면
                map[p.x][p.y] = 0;
                tempIce.set(i, new Pos(-1, -1));
            }
            else {
                // 기존 얼음 양만 감소
                map[p.x][p.y] -= meltAmount;
            }
        }

        ice = new ArrayList<>();

        for (Pos p : tempIce) {
            if (p.x != -1 && p.y != -1) {
                ice.add(p);
            }
        }

    }

    public static void BFS () {
        Queue<Pos> queue = new LinkedList<>();
        queue.add(ice.get(0));
        visit[ice.get(0).x][ice.get(0).y] = true;

        while (!queue.isEmpty()) {
            Pos poll = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = poll.x + dirX[i];
                int nextY = poll.y + dirY[i];

                if (nextX < 0 || nextX >= x || nextY < 0 || nextY >= y) {
                    continue;
                }
                if (map[nextX][nextY] == 0) {
                    continue;
                }
                if (visit[nextX][nextY]) {
                    continue;
                }
                visit[nextX][nextY] = true;
                queue.add(new Pos(nextX, nextY));

            }

        }
    }

    public static class Pos {
        int x;
        int y;
        Pos (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}