BaekJoon 7576. 토마토(Java)(BFS)(실버1)

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

7576번: 토마토

풀이 과정

- pair객체는 필드를 3개 가진다. 좌표(row, col)와 date. 여기서 date는 bfs를 하면서 +1씩되는 날짜를 의미

- 익은 토마토를 미리 찾아놓고 Queue에 저장.

- 저장한 토마토를 하나씩 꺼내면서 BFS시작.

- BFS과정을 거치면 날짜가 1씩 커지면서 모든 토마토를 익게하고, 다익었다는 가정하에 가장 큰 maxDate가 정답.

 

소스코드

package 백준;

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

public class Ex_7576 {
	// 실버1 토마토 bfs 문제 https://www.acmicpc.net/problem/7576
	private static class Pair {
		int row;
		int col;
		int date;

		public Pair(int row, int col, int date) {
			this.row = row;
			this.col = col;
			this.date = date;
		}
	}

	private static int N;
	private static int M;
	private static int[][] map;
	private static int maxDate = 0;
	private static Queue<Pair> q = new LinkedList<Pair>();
	private static int[] dr = { -1, 1, 0, 0 };
	private static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		map = new int[N][M]; // 인덱스에 맞추기위해서
		for (int row = 0; row < N; row++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int col = 0; col < M; col++) {
				map[row][col] = Integer.parseInt(st.nextToken());
				if (map[row][col] == 1) { // 1을 미리 찾아 놓는다.
					q.offer(new Pair(row, col, 0));
				}
			}
		}
		bfs(); // 이 메소드를 거치면 maxDate에 토마토를 다 익히는데 며칠이 걸리는지가 저장됨

		// 답 체크
		boolean check = true;
		outerloop: for (int row = 0; row < N; row++) {
			for (int col = 0; col < M; col++) {
				if (map[row][col] == 0) {
					check = false;
					break outerloop;
				}
			}
		}
		int answer = check ? maxDate : -1;

		bw.write(answer + "");
		bw.close();
		br.close();
	}

	private static void bfs() {
		while (!q.isEmpty()) {
			Pair temp = q.poll();
			maxDate = Math.max(maxDate, temp.date);
			for (int i = 0; i < 4; i++) {
				int tr = temp.row + dr[i];
				int tc = temp.col + dc[i];
				if (tr >= 0 && tc >= 0 && tr < N && tc < M && map[tr][tc] == 0) {
					map[tr][tc] = 1;
					q.offer(new Pair(tr, tc, temp.date + 1));
				}
			}
		}

	}
}