[JAVA] 백준 7576번: 토마토

요구사항

토마토가 모두 익는데 걸리는 최소 날짜를 출력하라

 

제한사항

익은 토마토에서 상, 하, 좌, 우에 위치한 안 익은 토마토는 다음날 익음

토마토가 모두 익지 못하는 상황이면 -1을 출력

처음부터 모두 익은 상태이면 0을 출력

 

문제 해설

최소 날짜를 구하는 문제로 BFS를 이용하여야 한다.

DFS로 풀 경우에는 최소 날짜를 구할 수 없다.

방문한 경로를 재 방문하는 형태로 문제를 풀 경우에는 DFS가 아닌 브루트포스를 이용한 문제 풀이이다.

브루트포스를 이용할 경우에는 시간 초과 에러가 발생한다.

 

dist[][] = 익는 날짜를 입력

visitInfo[][] = 해당 좌표에 위치한 토마토가 큐에 들어갈 수 있다면 true, 큐에 들어갈 수 없다면 false (중복하여 들어가는 것을 방지)

aryH[], aryW[] = 해당 좌표에 위차한 토마토에서 상, 하, 좌, 우에 위치한 토마토의 위치를 쉽게 넣기 보정 값이 존재하는 어레이

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class baekjoon7576_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] tomatoState = new int[n][m];
        Boolean[][] visitInfo = new Boolean[n][m];

        int[] aryH = { 0, 0, 1, -1 };
        int[] aryW = { 1, -1, 0, 0 };

        Queue<int[]> q = new LinkedList<>();
        int[][] dist = new int[n][m];
		
        // input 값을 집어 넣는다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int state = sc.nextInt();
                tomatoState[i][j] = state;
                if (state == 1) {
                    q.add(new int[] { i, j });
                    visitInfo[i][j] = false;
                    dist[i][j] = 1;
                    continue;
                }
                visitInfo[i][j] = true;
            }
        }


        while (!q.isEmpty()) {
            int[] location = q.poll();
            int h = location[0];
            int w = location[1];

            // 익은 토마토에서 상, 하, 좌, 우에 위치한 토마토 확인
            for (int i = 0; i < 4; i++) {
                int newH = h + aryH[i];
                int newW = w + aryW[i];
                // 새로운 위치가 어레이의 위치를 벗어나지 않으며, 방문한 적이 없을 경우에만 적용
                if (newW >= 0 && newH >= 0 && newW < m && newH < n && visitInfo[newH][newW]
                        && tomatoState[newH][newW] == 0) {
                    q.add(new int[] { newH, newW });
                    visitInfo[newH][newW] = false;
                    tomatoState[newH][newW] = 1;
                    dist[newH][newW] = dist[h][w] + 1;
                }
            }
        }
        int res = 0;
        boolean isImpossible = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
            	// 아직 안 익은 토마토가 존재하는 경우
                if (tomatoState[i][j] == 0) {
                    isImpossible = true;
                }
                if (dist[i][j] > res) {
                    res = dist[i][j];
                }
            }
        }
        
        // 안 익은 토마토가 존재하는 경우
        if (isImpossible) {
            System.out.println(-1);
        } else {
        	// 토마토가 익는 데 걸리는 최소 day
            System.out.println(res - 1);
        }
    }

}