[JAVA] 백준 알고리즘 7576 : 토마토 (BFS)

문제

소스

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

public class Main {

	static int n,m,x,y,_x,_y,result;
	static int map[][];
	static boolean visit[][];
	static int dx[] = {0, 1, 0, -1}; // 우, 하, 좌, 상
	static int dy[] = {1, 0, -1, 0};
	static Queue<Integer> qx = new LinkedList<Integer>();
	static Queue<Integer> qy = new LinkedList<Integer>();
	
	public static void bfs() {
		result = 0;
		
		while (!qx.isEmpty() && !qy.isEmpty()){
			
			x = qx.poll();
			y = qy.poll();

			visit[x][y] = true;
			
			for (int i=0; i<4; i++) {
				_x = x + dx[i];
				_y = y + dy[i];

				if (_x >= 0 && _y >= 0 && _x < m && _y < n) {
					if (map[_x][_y] == 0 && visit[_x][_y] == false){
						qx.add(_x);
						qy.add(_y);
						visit[_x][_y] = true;
						map[_x][_y] = map[x][y] + 1;
						result = map[_x][_y];
					}
				}
			} 
		}

		// 익지 않은 토마토가 있는지 체크
		for (int i=0; i<m; i++){
			for (int j=0; j<n; j++){
				if (map[i][j] == 0){
					result = -1;
				}
			}
		}
		
		if (result > 0){
			System.out.println(result-1);
		} else {
			System.out.println(result);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[m][n];
		visit = new boolean[m][n];
		int temp;
		
		for (int i=0; i<m; i++) {
			for (int j=0; j<n; j++) {
				temp = sc.nextInt();
				map[i][j] = temp;
				
				if (temp == 1) { // 익은 토마토
					qx.add(i);
					qy.add(j);
				}
			}
		}
		
		bfs();
	}
}

출처

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