[백준] 7576번: 토마토

문제링크 : https://www.acmicpc.net/problem/7576

 

문제풀이

bfs로 풀 수 있는 문제이다.

 

1. 익은 토마토(값이 1인 것)들을 찾아 큐에 넣고, 방문 체크를 한다.

2. 큐에 있는 값들을 하나씩 빼면서 왼쪽, 오른쪽, 앞, 뒤 네 방향에 익지 않은 토마토가 있는지 체크한다.

3. 익지 않은 토마토(값이 0인 것)가 있으면, 큐에 넣고 방문 체크를 한다.

4. 큐에 값이 없을 때까지 반복한다.

 

큐에 값이 없을 때까지 작업을 반복했는데도 0인 토마토가 있으면 토마토가 모두 익지 못하는 상황이므로 -1을 출력한다.

 

 

소스코드

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

public class p_7576 {
	static int M, N;
	static int[][] arr;
	static boolean[][] visit;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			Arrays.fill(visit[i], false);
		}

		arr = new int[N][M];
		boolean ripen = true;
		for (int i = 0; i < N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str);
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				
				if (arr[i][j] == 0) ripen = false;
			}
		}

		// 모두 익어있는 경우
		if (ripen) {
			System.out.println(0);
		}
		else {
			System.out.println(bfs());
		}
	}
	
	public static int bfs() {
		Queue<Position> queue = new LinkedList<Position>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++ ) {
				if (arr[i][j] == 1) {
					queue.offer(new Position(i, j));
					visit[i][j] = true;
				}
			}
		}
		
		int day = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Position next = queue.poll();
				for (int j = 0; j < 4; j++) {
					int x = next.x + dx[j];
					int y = next.y + dy[j];
					if (x >= 0 && x < N && y >= 0 && y < M) {
						if (arr[x][y] == 0 && !visit[x][y]) {
							queue.offer(new Position(x, y));
							arr[x][y] = 1;
							visit[x][y] = true;
						}
					}
				}
			}
			day++;
		}
		
		boolean ripen = true;
		
		// 다 익었는지 체크
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 0) {
					ripen = false;
				}
			}
		}
		
		if (ripen) return day - 1;
		
		return -1;
	}
}

class Position {
	int x;
	int y;
	Position (int x, int y) {
		this.x = x;
		this.y = y;
	}
}