[백준 7576] 토마토 풀이 (JAVA)

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

7576번: 토마토

 

BFS를 사용하여 푸는 문제였다. 

1. dot 클래스를 생성하여 익은 토마토가 있는 x,y좌표를 큐에 저장한다.

2. 큐의 값을 poll하여 동서남북으로 안익은 토마토가 있는지 확인한 후,

안익은토마토 위치에는 익은 일수를 넣어준다. ( 첫날 익었으면 1, 둘째날은 첫날 익은 토마토 위치의 값 +1 ...)

그리고 큐에 add 하고 큐가 비어질때까지 반복한다.

3. 모든 토마토가 익었는지 확인한다.

익지 않은 토마토가 있다면 result에 -1을 넣고 return한다.

모두 다 익었다면 가장 큰 값(마지막 일수) -1을 한 값을 출력한다.

(큰 값 -1을 하는 이유는 입력받은 익은 토마토의 값은 1이기 때문에, 첫날 익은 토마토의 최종값은 2일 것이기 때문이다.)

 

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

public class Main {
	static int n, m, result;
	static int[][] arr;
	static int[] dx = { -1, 1, 0, 0 }; //동서남북 확인하기 위한 배열
	static int[] dy = { 0, 0, -1, 1 };

	static class dot {
		int x;
		int y;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		arr = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		bfs();
		System.out.println(result==-1?result:result-1);
	}

	static void bfs() {
		Queue<dot> q = new LinkedList<dot>();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 1) {
					q.add(new dot(i, j));
				}
			}
		}
		while (!q.isEmpty()) {
			dot d = q.poll();
			for (int i = 0; i < 4; i++) {
				int xx = d.x + dx[i];
				int yy = d.y + dy[i];
				if (xx < 0 || yy < 0 || xx >= n || yy >= m) 
					continue;
				if (arr[xx][yy] != 0) //토마토가 없는 위치거나 익은 토마토가 있는 위치면 다음으로
					continue;
				arr[xx][yy] = arr[d.x][d.y] + 1; //익은 일수를 넣어준다
				q.add(new dot(xx, yy));
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j]==0) { //안익은 토마토가 있다면 -1
					result=-1;
					return;
				}
				result =Math.max(arr[i][j],result);
			}
		}
	}

}