baekjoon 7576. 토마토 (Java, 설명포함)

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

문제

1이 익은 토마토, 0이 익지 않은 토마토, -1이 빈칸일 때 날이 지날수록 익은 토마토 상하좌우의 토마토는 익는다.
모든 토마토가 익을 때 까지 걸리는 일수를 구하라
(시작 부터 모두 익었으면 0, 모두 익을 수 없는 경우 -1)

풀이

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt(), n = sc.nextInt();

    int[][] tomatos = new int[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tomatos[i][j] = sc.nextInt();
        }
    }
    for (int i = 0; i < m * n; i++) {
        boolean isGood = true;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (tomatos[j][k] == 0) {
                    isGood = false;
                    break;
                }
            }
        }
        int[][] goodedTomatos = new int[n][m];
        if (isGood) {
            System.out.println(i);
            return;
        } else {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (goodedTomatos[j][k] == 1)
                        continue;
                    goodedTomatos[j][k] = tomatos[j][k];
                    if (tomatos[j][k] == 1) {
                        if (j > 0) {
                            if (tomatos[j - 1][k] == 0)
                                goodedTomatos[j - 1][k] = 1;
                        }
                        if (k > 0) {
                            if (tomatos[j][k - 1] == 0)
                                goodedTomatos[j][k - 1] = 1;
                        }

                        if (j < n - 1) {
                            if (tomatos[j + 1][k] == 0)
                                goodedTomatos[j + 1][k] = 1;
                        }
                        if (k < m - 1) {
                            if (tomatos[j][k + 1] == 0)
                                goodedTomatos[j][k + 1] = 1;
                        }
                    }
                }
            }
        }


        boolean isFailed = true;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                if (tomatos[j][k] != goodedTomatos[j][k]) {
                    isFailed = false;
                }
            }
        }
        if (isFailed) {
            System.out.println(-1);
            return;
        } else {
            tomatos = goodedTomatos;
        }
    }
}

무식한 풀이, 참고만 하세요

public static void main(String[] args) {
    class Tomato {
        int x, y, day;

        public Tomato(int x, int y, int day) {
            this.x = x;
            this.y = y;
            this.day = day;
        }
    }
    Queue<Tomato> ripeTomatos = new LinkedList<>();
    int[] xValues = {-1, 0, 1, 0};
    int[] yValues = {0, 1, 0, -1};

    int day = 0;

    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt(), n = sc.nextInt();

    int[][] tomatos = new int[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int tomato = sc.nextInt();
            tomatos[i][j] = tomato;
            if (tomato == 1) {
                ripeTomatos.add(new Tomato(j, i, 0));
            }
        }
    }

    while (!ripeTomatos.isEmpty()) {
        Tomato tomato = ripeTomatos.poll();
        for (int i = 0; i < 4; i++) {
            if (tomato.x + xValues[i] >= 0 && tomato.x + xValues[i] < m
                    && tomato.y + yValues[i] >= 0 && tomato.y + yValues[i] < n) {
                if (tomatos[tomato.y + yValues[i]][tomato.x + xValues[i]] == 0) {
                    tomatos[tomato.y + yValues[i]][tomato.x + xValues[i]] = 1;
                    day = tomato.day + 1;
                    ripeTomatos.add(
                            new Tomato(tomato.x + xValues[i], tomato.y + yValues[i], day));

                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tomatos[i][j] == 0) {
                System.out.println(-1);
                return;
            }
        }
    }
    System.out.println(day);
}

문제의 핵심은 Queue를 사용해 익은 토마토를 캐시처럼 담아두고, 날이 흐름에 따라 익는 토마토 또한 다음 날에는 상하좌우 익지 않은 토마토에 영향을 주기 때문에
시작 시점의 익은 토마토를 Queue에 넣고, Queue를 비우면서 상하좌우 토마토가 익게 하고 익은 토마토는 Queue에 넣습니다.
큐가 비어졌을 때에는 가능한 모든 토마토를 익게 했을 때이며 이 때 익지 않은 토마토가 있다면 -1, 불가능입니다.