[백준] 7576 토마토

문제 출처: www.acmicpc.net/problem/7576

7576번: 토마토

: 토마토를 보관하는 큰 창고가 있고, 그 안에 있던 토마토들은 익은 토마토를 중심으로 하루가 지날 때마다 익은 토마토에 인접한 토마토들이 함께 익는다.

: 인접한 토마토는 대각선을 포함하지 않는다.

: 익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 없다면 -1로 그 칸의 값이 주어진다.

: 모든 토마토가 익기 까지 걸리는 최소 날짜를 출력해야하는데 만약 모든 토마토가 익어있는 상태라면 0을 출력하고 토마토가 모두 익지 못하는 상황이면 -1을 출력한다.

 

: 날짜는 나로 인해 익을 수 있는 토마토를 Queue에 넣을 때마다 1씩 증가시켜주면 된다.

: 처음에 토마토 배열을 입력받을 때 세어놓았던 안익은 토마토의 개수를 사용하여 while문을 돌 때 그 개수와 새롭게 익은 토마토의 개수가 같아지면 그 때까지 걸렸던 날짜를 반환한다.

: 만약 while문을 돌면서 새로 익은 토마토 개수가 원래 익지 않았던 토마토 개수와 같아지지 않으면 모두 익지 못하는 상황이므로 -1을 출력한다.

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

public class 토마토7576 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int[][] tomato;
	static boolean[][] visited;
	static int R, C;

	public static void main(String[] args) throws IOException {
		// 토마토 상자의 열과 행 길이 입력받기
		st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

		tomato = new int[R][C];
		visited = new boolean[R][C];
		// 토마토의 상태들을 입력받으면서
		// 익지 않은 토마토의 개수와
		// 익은 토마토가 처음 시작하는 좌표 저장해놓기
		int cnt = 0;
		// 처음부터 익은 토마토 들의 좌표
		ArrayList<int[]> list = new ArrayList<>();
		boolean flag = false;
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				tomato[i][j] = Integer.parseInt(st.nextToken());
				if (tomato[i][j] == 1) list.add(new int[] {i, j});
				if (tomato[i][j] == 0) cnt++;
			}
		}

		int ans = 1243;
		if(cnt == 0) ans = 0;
		else {
			ans = bfs(list, cnt);
		}
		System.out.println(ans);
	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int count = 0;
	private static int bfs(ArrayList<int[]> list, int cnt) {
		// bfs 방식으로 익은 토마토에 접근하면서
		int date = 0;
		Queue<int[]> q = new LinkedList<>();
		for(int i = 0, size = list.size(); i < size; i++) {
			int[] temp = list.get(i);
			q.offer(new int[] {temp[0], temp[1], 0});
			visited[temp[0]][temp[1]] = true;
		}

		// 날짜를 카운팅하고
		// 익은 토마토의 개수를 세고
		// 그 개수가 익지 않은 토마토개수와 같아지면 멈추기
		while (!q.isEmpty()) {
			int[] location = q.poll();
;
			for (int i = 0; i < 4; i++) {
				int nr = location[0] + dr[i];
				int nc = location[1] + dc[i];

				if (nr < 0 || nr >= R || nc < 0 || nc >= C || tomato[nr][nc] == -1 || visited[nr][nc])
					continue;
				
				visited[nr][nc] = true;
				if(tomato[nr][nc] == 0) count++;
				tomato[nr][nc] = 1;
				q.offer(new int[] {nr, nc, location[2]+1});
			}
			date++;
			if(count == cnt) return location[2]+1;
		}
		return -1;
	}
}