[백준] 7576 토마토 (JAVA)

풀이

 이 문제는 이 전에 풀었던 미로탐색(2178)과 궤를 같이 하는 문제이다. 나는 미로탐색처럼 간단할줄 알고 덤볐으나 생각할게 조금있었다. 우선 이 문제에서는 시작점이 주어지지 않았으며 하루가 지날때 마다 영향을 받는 토마토는 다양해서 조금 더 생각한것 같다. 그리고 반복문을 생각보다 많이 돌려 문제를 풀면서 시간초과를 많이 신경 썼다.

 

 알고리즘은 다음과 같다. 처음에 box라는 2차원 배열에 토마토의 위치등을 저장할때 토마토가 있는 곳들, 즉 1로 입력값이 주어지는 위치는 바로바로 큐에 집어넣었다. 그리고 저장이 전부 끝난후에는 바로 BFS함수로 들어가서 그래프 탐색을 진행하였다. 참고로 왜 DFS가 아닌 BFS를 사용했는지 궁금하다면 https://goto-pangyo.tistory.com/23 이 글을 읽어보면 이해가 될것이다. 무엇보다도 눈으로 읽기만 하는것 보다는 연습장같은곳에 직접 적어보는것이 더 이해하기 빠를것이다. 다시 문제풀이로 돌아와서 나는 box값을 갱신해주었다. 즉 현재위치의 토마토가 익을려면 얼마나 걸리는지 적어 놓았다. 그렇기에 현재 위치에서 다음 위치로 갈때는 복잡한 수식을 사용할 필요 없이 현재 위치의 box값에서 +1을 해주어 저장을 해주면 다음 위치의 토마토가 익을때까지 걸리는 시간이 될것이다. 그렇게 그래프를 탐색하다 queue가 비게 된다면 탐색을 종료 하고 나오게 된다. 또한 여기서 나는 한가지 더 해준것이 있는데 토마토가 빈 공간으로 둘러쌓여 익지 못했는 경우이다. 그냥 단순히 하나씩 탐색해가며 만약 box의 값이 0이 있다면 즉시 멈추고 -1을 출력하고 프로그램을 종료 시켰다.

 

여담으로 처음에는 만약 전부 익은 토마토가 담기는 경우까지 따로생각해 주었는데 찬찬히 생각해보니 그럴필요가 없었다. 그 이유인 즉슨 나는 처음에 입력 받으면서 입력값이 1인경우(토마토가 익은상태로 담기는 경우)는 queue에 넣으면서 방문 표시를 해두었는데 만약 전부 익은 경우라면 queue에 새로 담기는 경우가 없고 새로 담기는 경우가 없으면 box의 값을 갱신하는 일도 없기에 전부 익은 토마토가 담기는 경우는 크게 신경쓰지 않고 해도된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


class Main {

    public static int M, N;
    public static int[][] box;
    public static boolean[][] visited;
    public static int[] dr_x = {-1, 0, 1, 0};
    public static int[] dr_y = {0, 1, 0, -1};
    public static int cnt;
    public static Queue<point> queue = new LinkedList<point>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        box = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
                if (box[i][j] == 1) {
                    queue.offer(new point(i, j));
                    visited[i][j] = true;
                }
            }
        }

        BFS();

    }

    public static void BFS() {
        while (!queue.isEmpty()) {
            point cur = queue.poll();
            cnt = box[cur.getX()][cur.getY()];
            for (int i = 0; i < 4; i++) {
                int temp_x = cur.getX() + dr_x[i];
                int temp_y = cur.getY() + dr_y[i];

                if (temp_x < 0 || temp_y < 0 || temp_x >= N || temp_y >= M
                        || box[temp_x][temp_y] == -1 || visited[temp_x][temp_y]) {
                    continue;
                }

                box[temp_x][temp_y] = box[cur.getX()][cur.getY()] + 1;

                queue.offer(new point(temp_x, temp_y));
                visited[temp_x][temp_y] = true;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (box[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        System.out.println(cnt - 1);

    }

    static class point {
        private int x;
        private int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

}