백준 7576번 토마토 JAVA 구현해보기

---

```

백준 7576번 토마토 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 7576번 풀이

---

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

7576번: 토마토

 

백준 7576번 토마토는

난이도 골드 등급의 문제로서

 

너비 N 높이 M의 1 X 1 크기의 토마토 상자가 주어지고

각칸에 토마토 혹은 장벽이 있으며

벽은 -1

익은 토마토는 1

익지 않은 토마토는 0이고

익은 토마토는 하루에 한 번 상하좌우의 토마토를 익게 만든다고 할 때

모든 토마토가 익는데 걸리는 날을 계산하고

처음부터 모두 익어 있으면 0 

모두 익지 못하면 -1을 출력하는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

BFS를 이용하여서 풀었으며

값이 작은 토마토부터 하나씩 큐에 넣고

돌리면서 날짜를 계산하였습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input01 = br.readLine().split(" ");

        final int width = Integer.parseInt(input01[0]);
        final int height = Integer.parseInt(input01[1]);
        int[][] box2DArr = new int[height][width];

        for (int i = 0; i < height; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < width; j++) {
                box2DArr[i][j] = Integer.parseInt(input[j]);
            }
        }

        System.out.print(solution(width, height, box2DArr));
    }

    private static int solution(int width, int height, int[][] box2DArr) {

        Queue<Position> queue = new LinkedList<>();
        final int[][] dyDx = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        // Que 초기 값 입력
        IntStream.range(0, height).forEach(i -> IntStream.range(0, width).forEach(j -> {
            if (box2DArr[i][j] == 1) {
                queue.offer(new Position(i, j));
            }
        }));

        int result = -1;
        if (!queue.isEmpty()) {
            // 박스를 돌면서 인접 값들을 BFS 적으로 순회
            while (!queue.isEmpty()) {
                Position curPos = queue.poll();

                IntStream.range(0, 4).forEach(i -> {
                    final int nextY = dyDx[i][0] + curPos.getY();
                    final int nextX = dyDx[i][1] + curPos.getX();

                    if (isInside(nextY, nextX, width, height) && box2DArr[nextY][nextX] == 0) {
                        box2DArr[nextY][nextX] = box2DArr[curPos.getY()][curPos.getX()] + 1;
                        queue.offer(new Position(nextY, nextX));
                    }
                });
            }

            // 못가는 부분이 있으면 0 발견
            // 소요 날짜 확인
            outerloop:
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (box2DArr[i][j] == 0) {
                        result = -1;
                        break outerloop;
                    } else if (result < box2DArr[i][j] - 1) {
                        result = box2DArr[i][j] - 1;
                    }
                }
            }
        }


        return result;
    }

    private static boolean isInside(int yPos, int xPos, int width, int height) {
        return (-1 < yPos && -1 < xPos && yPos < height && xPos < width);
    }

    private static class Position {
        private final int x;
        private final int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

// https://codemasterkimc.tistory.com/

 

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---