[알고리즘 문제] 백준7576 - 토마토

 

정사각형 박스에 익은 토마토와 익지 않은 토마토가 들어가 있다. 하루가 지날 때 마다, 익은 토마토의 상/하/좌/우 위치에 있는 익지 않은 토마토가 익게 된다. 이런 규칙으로 박스안의 토마토는 하나씩 익어 갈 때, 며칠이 지나면 다 익게 되는지 그 최소 일 수를 구하는 문제이다.

 

문제 해결,

1. 먼저 익은 토마토(x,y,day)를 큐에 넣는다.

2.하나씩 뺴면서 주변에 익지 않은 토마토가 있다면 익지 않은 토마토를 하나씩 넣어준다.

3. 큐가 빌떄까지 계속 한다.

 

여기서, day를 어떻게 확인할 까 고민을 했는데 이는 다른 사람의 코드를 보고 참고했다.

처음 입력에서 익은 토마토의 day를 0으로 초기화 하고 넣어준다. 그리고 que에서 토마토를 하나씩 꺼내면서 주변 익지 않은 토마토를 큐에 넣을 때, 현재 꺼낸 토마토의 day+1값을 해준다. 그리고 마지막 출력할 땐 day값을 출력해준다.

 

그리고 문제에서 "저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다" 라고 되어있는데 이 부분은 어쨋든 배열에 0,1이 있는지 검사해야 하기 때문에 check()함수로 분리하였다.

 

이 문제는 bfs를 이해하는데 좋은 문제라고 생각한다, day를 확인하는 것처럼 bfs로 탐색할 때, 각 depth를 어떻게 구할 수 있을까? 를 생각할 수 있다는 점에서 괜찮은 문제였다.

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int width = sc.nextInt();
        int height = sc.nextInt();
        int[][] arr = new int[height][width];

        Queue<Tomato> que = new LinkedList<Tomato>();
        int startX, startY;
        int y, x;
        int n;
        int count = 0;

        for (y = 0; y < height; y++) {
            for (x = 0; x < width; x++) {
                n = sc.nextInt();
                if (n == 1) {
                    que.offer(new Tomato(x, y, 0));
                }
                arr[y][x] = n;
            }
        }

        if (!check(0, arr)) { // 처음부터 모두 익어있는 상태인지 검사
            System.out.println(0);
            return;
        }

        // 우,하,좌,상
        int[] dx = { 1, 0, -1, 0 };
        int[] dy = { 0, 1, 0, -1 };

        Tomato tmt;
        int day = 0;

        while (!que.isEmpty()) {
            tmt = que.poll();
            day = tmt.day;
            for (int i = 0; i < 4; i++) {

                int newY = tmt.y + dy[i];
                int newX = tmt.x + dx[i];

                if (newY < 0 || newY > height - 1 || newX < 0 || newX > width - 1) { // 배열을 벗어난 경우
                    continue;
                }

                if (arr[newY][newX] == 0) {
                    arr[newY][newX] = 1;
                    que.offer(new Tomato(newX, newY, day + 1));
                }
            }
        }
        if (check(0, arr)) { // 탐색을 했지만 아직 익지 못한 토마토가 있으면
            System.out.println(-1);
            return;
        }
        System.out.println(day);
    }

    static boolean check(int n, int[][] arr) {
        for (int y = 0; y < arr.length; y++) {
            for (int x = 0; x < arr[0].length; x++) {
                if (arr[y][x] == n) {
                    return true;
                }
            }
        }
        return false;
    }
}

class Tomato {
    int x;
    int y;
    int day;

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