[알고리즘-PS] 백준 7576번 토마토 자바 문제풀이

문제

해당 포스팅은 백준의 7576번 토마토 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

7576번: 토마토

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 BFS 를 이용해서 풀 수 있는 문제이다.

 

각각의 노드는 4방으로 상, 하, 좌, 우 로 연결된 그래프를 띄고 있는데, visited 라는 방문 체크 flag 가 필요 없는 문제이다.

 

하루에 1씩 썩어간다면 1 혹은 그 이상의 수가 존재한다면 이미 방문한 것으로 보고 넘어가도 되는 것이다.

 

정답 코드

public class Main {

    private static int[][] arr;
    private static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

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

    private static Queue<Position> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int n = Integer.parseInt(nm[0]); // x
        int m = Integer.parseInt(nm[1]); // y

        arr = new int[m][n];

        for (int i = 0; i < arr.length; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                arr[i][j] = Integer.parseInt(inputs[j]);
                if(arr[i][j] == 1) {
                    queue.add(new Position(j, i));
                }
            }
        }

        decay(n, m);

        int answer = 0;

        for (int i = 0; i < arr.length; i++) {
            for(int value : arr[i]) {
                if(value == 0) {
                    System.out.println(-1);
                    return ;
                }
                answer = Math.max(answer, value);
            }
        }
        System.out.println(answer - 1);
    }

    private static void decay(int n, int m) {
        while(!queue.isEmpty()) {
            Position front = queue.remove();
            for (int i = 0; i < 4; i++) {
                int xx = xPos[i] + front.x;
                int yy = yPos[i] + front.y;

                if(0 <= xx && xx < n && 0 <= yy & yy < m) {
                    if(arr[yy][xx] == 0) {
                        arr[yy][xx] = arr[front.y][front.x] + 1;
                        queue.add(new Position(xx, yy));
                    }
                }
            }
        }
    }

    private static class Position {
        int x;
        int y;

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

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.