[백준]7569- 토마토 문제 풀이(Java,자바)

 

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

 

들어가며

이 문제는 유사한 문제가 있다.

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

제목은 같은 토마토이지만, 7569 토마토는 3차원 상자라 더 구하기가 어렵다.

비슷한 접근 방식을 사용하면 된다.

 

bfs의 대표격인 문제이다.

코드

package solved.ac.class3;

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

public class 백준7569_토마토 {

    static int[][] dir = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
    //h n m
    static int[][][] arr;
    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());

        arr = new int[h][n][m];
        for (int i = 0; i < h; i++){
            for (int j = 0; j < n; j++){
                int[] tomatoArray = Arrays.stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray();
                arr[i][j] = tomatoArray;
            }
        }
        Queue<Position> queue = new ArrayDeque<>();
        int blankCount = 0;
        for (int i = 0; i < h; i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k < m; k++){
                    if (arr[i][j][k] == 1){
                        queue.add(new Position(i,j,k));
                    }
                    if (arr[i][j][k] == -1){
                        blankCount++;
                    }
                }
            }
        }
        if (queue.size() == h * n * m-blankCount){
            System.out.println(0);
            return;
        }

        int result = bfs(queue, n, m,h);
        for (int i = 0; i < h; i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k < m; k++){
                    if (arr[i][j][k] == 0){
                        System.out.println(-1);
                        return;
                    }
                }
            }
        }
        System.out.println(result-1);
    }

    private static int bfs(Queue<Position> queue, int n, int m, int h){
        int count = 0;

        while (!queue.isEmpty()){
            int size = queue.size();
            for (int s = 0; s < size; s++){
                Position position = queue.poll();

                for (int i = 0; i < 6; i++){
                    int nx = position.x + dir[i][0];
                    int ny = position.y + dir[i][1];
                    int nz = position.z + dir[i][2];
                    if (isValidMove(nx,ny,nz,n,m,h)){
                        arr[nz][ny][nx] = 1;
                        queue.add(new Position(nz,ny,nx));
                    }
                }
            }
            count++;
        }
        return count;
    }

    private static boolean isValidMove(int nx, int ny, int nz, int n, int m, int h){
        if (nx < 0 || ny < 0 || nz < 0 || nx >= m || ny >= n || nz >= h || arr[nz][ny][nx] != 0){
            return false;
        }
        return true;
    }
    static class Position{
        int z;
        int y;
        int x;
        public Position(int z, int y, int x) {
            this.z = z;
            this.y = y;
            this.x = x;
        }
    }
}

풀이

bfs를 이용해서 모든 배열을 1로 만들어주는 것이 목표이다.

그리고 그 과정 속에서 몇 일이 지났는지 계산하면 끝이다.

arr = new int[h][n][m];

토마토의 정보를 저장하기 위해서 3차원 배열을 사용한다.

높이, 세로, 가로 순인데 높이만 앞에 있다면 뒤는 바꿔도 무방하다.

 

static int[][] dir = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};

3차원 배열을 사용하니까 방향도 6개로 늘어났다.

h+-1 , n+-1, m+-1 이라고 생각하면 된다.

이것 또한 순서는 크게 상관없다. 알아보기 좋을 뿐이다. (어차피 모든 방향을 다 돌아야하므로)

Queue<Position> queue = new ArrayDeque<>();
int blankCount = 0;
for (int i = 0; i < h; i++){
    for (int j = 0; j < n; j++){
        for (int k = 0; k < m; k++){
            if (arr[i][j][k] == 1){
                queue.add(new Position(i,j,k));
            }
            if (arr[i][j][k] == -1){
                blankCount++;
            }
        }
    }
}

3차원 배열 입력을 받고나면 토마토를 찾아 준다.

이때, 입력받은 토마토들이 모두 익은 상황을 고려하기 위해 -1의 개수 또한 계산해준다.

if (queue.size() == h * n * m-blankCount){
    System.out.println(0);
    return;
}

입력받은 토마토들이 모두 익은 상황을 예외처리하는 모습이다.

전체 개수에서 빈칸을 뺀 것과 큐에 들어간 토마토들의 개수가 같으면 모두 익은 것이다.

private static int bfs(Queue<Position> queue, int n, int m, int h){
    int count = 0;

    while (!queue.isEmpty()){
        int size = queue.size();
        for (int s = 0; s < size; s++){
            Position position = queue.poll();

            for (int i = 0; i < 6; i++){
                int nx = position.x + dir[i][0];
                int ny = position.y + dir[i][1];
                int nz = position.z + dir[i][2];
                if (isValidMove(nx,ny,nz,n,m,h)){
                    arr[nz][ny][nx] = 1;
                    queue.add(new Position(nz,ny,nx));
                }
            }
        }
        count++;
    }
    return count;
}

private static boolean isValidMove(int nx, int ny, int nz, int n, int m, int h){
        if (nx < 0 || ny < 0 || nz < 0 || nx >= m || ny >= n || nz >= h || arr[nz][ny][nx] != 0){
            return false;
        }
        return true;
    }

 

평범한 bfs이다. 특별한 건 없다.

여기서 queue의 크기는 메모리로 저장해야 한다. 반복문을 도는 과정 속에서 동적으로 변하기 때문이다.

 

for (int i = 0; i < h; i++){
    for (int j = 0; j < n; j++){
        for (int k = 0; k < m; k++){
            if (arr[i][j][k] == 0){
                System.out.println(-1);
                return;
            }
        }
    }
}
System.out.println(result-1);

모두 돌았는데 안익은 토마토가 있다면 -1을 문제에서 출력하라고 했으므로 그렇게 한다.

아닌 경우 결과를 표시하는데 여기서 -1을 해야 하는 이유는 처음 익은 토마토를 넣었을 때도 하루가 추가되기 때문이다.

그렇기에 -1을 해야 정상적인 값이 표시가 된다.