[백준 / 골드5] 7576 토마토 (Java)

문제 보기

사용한 것

• 익은 토마토 주변의 덜 익은 토마토를 찾기 위한 BFS
• 토마토의 타입(익음, 덜 익음, 빈 공간), 좌표, 날짜를 저장하기 위한 Tomato

풀이 방법

• 입력 받으면서 all에 전체 토마토 수, ripe에 익은 토마토 수, box에 입력 값으로 Tomato 생성하여 저장한다.
• 만약 ripe가 all과 같다면 처음부터 모든 토마토가 익었으므로 0을 출력한다.
• box를 순회하며 q에 익은 토마토를 넣는다.
• 모두 익을 수 없는 경우 -1을 출력해야 하므로 day를 -1로 초기화한다.
• 큐에 원소가 존재하고 ripe가 all보다 작을때까지 BFS 돈다.
• 익은 토마토를 q에서 꺼낸 tomato의 좌표에서 방향 별로 box를 벗어나지 않고 덜 익은 토마토(nextTomato)를 발견하면
  • setter를 사용하여 덜 익은 토마토의 nextTomato.type을 익은걸로(1), nextTomato.day를 tomato.day + 1 로 교체한다.
  • ripe를 증가시키고 all과 같아지면 모두 익었으므로 day에 nextTomato.day를 넣고 break 한다.
• BFS를 수행하여 얻은 결과를 출력한다.

코드

public class Main {

    static int N;
    static int M;
    static Tomato[][] box;
    static int all;
    static int ripe;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        M = Integer.parseInt(line[0]);
        N = Integer.parseInt(line[1]);
        box = new Tomato[N][M];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int type = Integer.parseInt(st.nextToken());
                if (type == 0) {
                    all++;
                } else if (type == 1) {
                    ripe++;
                    all++;
                }
                box[i][j] = new Tomato(type, i, j, 0);
            }
        }

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

        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Tomato> q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Tomato tomato = box[i][j];
                if (tomato.type == 1) {
                    q.offer(tomato);
                }
            }
        }

        int day = -1;
        while (!q.isEmpty() && ripe < all) {
            Tomato tomato = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tomato.x + dx[i];
                int ny = tomato.y + dy[i];

                if (isOOB(nx, ny)) {
                    continue;
                }

                Tomato nextTomato = box[nx][ny];
                if (nextTomato.type == 0) {
                    nextTomato.setType(1);
                    nextTomato.setDay(tomato.day + 1);

                    if (++ripe == all) {
                        day = nextTomato.day;
                        break;
                    }

                    q.offer(nextTomato);
                }
            }
        }

        return day;
    }

    static boolean isOOB(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M) {
            return true;
        }

        return false;
    }
}

class Tomato {

    public int type;
    public int x;
    public int y;
    public int day;

    public Tomato(int type, int x, int y, int day) {
        this.type = type;
        this.x = x;
        this.y = y;
        this.day = day;
    }

    public void setType(int type) {
        this.type = type;
    }

    public void setDay(int day) {
        this.day = day;
    }
}