[백준] 7576번 토마토

 2차원 배열에 위치한 토마토가 4방향(동, 서, 남, 북)으로 퍼지면서 주변에 토마토들이 익어가는 문제 입니다. 전형적인 BFS 문제이라고 판단하였고 BFS를 이용해서 문제를 해결하였습니다. 초기에 입력된 정보에서 토마토의 위치를 큐에 넣어두고 BFS탐색을 시작하였습니다. 토마토가 이미 익었을 경우와 벽이 있는 경우에는 큐에 넣지 않았고 익지 않은 토마토를 큐에 넣고 현재 위치의 토마토가 익은 날짜 +1을 해서 몇일째에 토마토가 익었는지 2차원 배열에 표시하였습니다. 아래는 문제와 소스 코드 입니다.

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

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

public class Tomato {
	
	int[][] tomatoBox;
	int row, col;
	int[][] days;
	int[] dRow = {0,0,-1,1}, dCol = {-1,1,0,0};
	Queue<Pair<Integer, Integer>> q;
	
	void bfs(){
		Pair<Integer, Integer> tempPair;
		int nRow, nCol;
		int curRow, curCol;
		
		while(!q.isEmpty()){
			tempPair = q.poll();
			curRow = tempPair.x;
			curCol = tempPair.y;
			for(int i=0;i<4;i++){
				nRow = curRow + dRow[i];
				nCol = curCol + dCol[i];
				if(0 <= nRow && nRow < row && 0 <= nCol && nCol < col){
					if(tomatoBox[nRow][nCol] == 0 && days[nRow][nCol] == -1){
						tempPair = new Pair<Integer, Integer>(nRow, nCol);
						days[nRow][nCol]= days[curRow][curCol] + 1;
						tomatoBox[nRow][nCol] = 1;
						q.add(tempPair);
					}
				}
			}
		}
	}
	
	void solution() throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s;
		String[] arrS;
		
		Pair<Integer, Integer> tempPair;
		q = new LinkedList<Pair<Integer, Integer>>();
		
		s = bf.readLine();
		arrS = s.split(" ");
		row = Integer.parseInt(arrS[1]);
		col = Integer.parseInt(arrS[0]);
		tomatoBox = new int[row][col];
		days = new int[row][col];
		for(int i=0;i<row;i++){
			s = bf.readLine();
			arrS = s.split(" ");
			for(int j=0;j<col;j++){
				tomatoBox[i][j] = Integer.parseInt(arrS[j]);
				days[i][j] = -1;
				if(tomatoBox[i][j] == 1){
					tempPair = new Pair<Integer, Integer>(i,j);
					q.add(tempPair);
					days[i][j] = 0;
				}
			}
		}
		
		bfs();
		
		int ans = 0;
		for(int i=0;i<row;i++){
			for(int j=0;j<col;j++){
				if(days[i][j] > ans){
					ans = days[i][j];
				}
			}
		}
		for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (tomatoBox[i][j] == 0 && days[i][j] == -1) {
                    ans = -1;
                }
            }
        }
		
		System.out.println(ans);
		
	}

	public static void main(String[] args) throws IOException {
		Tomato m =new Tomato();
		m.solution();
	}
	
	class Pair<X, Y>{
		X x;
		Y y;
		
		public Pair(X x, Y y){
			this.x = x;
			this.y = y;
		}
		
	}

}