[자바] 백준 7576 - 토마토

처음 토마토 문제 풀었을 때는 '이렇게 꼼꼼하게 생각해야 하는 문제도 있다니..!'라면서 놀랐던 기억이 난다. 

 

이번에 문제 풀 때에는 토마토 여부와 토마토 종류를 담는 tomato[][]와 익기까지 걸리는 일수를 담은 day[][] 배열을 각각 만들었다.

오래 고민하기 싫어서 그랬는데 이전에 푼 방식을 보니 tomato[][]배열 하나로 끝냈다. 메모리도 훨씬 적게 들고, 시간도 덜 걸리니 배열 하나로 푸는 게 좋긴 한 것 같다.

익은 토마토가 있다면 1, 그냥 토마토가 있다면 0, 토마토가 없다면 -1의 값이 들어온다는 점에서 착안해 처음에 익은 토마토들을 BFS 큐에 넣을 때 무조건 dayCount를 2로 세팅해서 넣었다. 이렇게 하면 다음에 갈 곳의 토마토가 이미 익었는지 안 익었는지 한번 더 체크할 필요 없이 tomato[newN][newM]이 0이면 무조건 큐에 집어넣으면 된다.

이전에 짠 코드가 더 좋네 ㅎ

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

public class Main {

	public static int M;
	public static int N;
	public static int[][] tomato;
	public static Queue<int[]> queue = new LinkedList<int[]>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = null;
		str = br.readLine().trim().split(" ");
		M = Integer.parseInt(str[0]);
		N = Integer.parseInt(str[1]);
		
		tomato = new int[N][M];
		
		int totalTomato = 0;
		int rottenTomato = 0;
		for(int i=0;i<N;i++){
			str = br.readLine().trim().split(" ");
			for(int j=0;j<M;j++){
				tomato[i][j] = Integer.parseInt(str[j]);
				
				switch(tomato[i][j]){
				case 0:
					totalTomato++;
					break;
				case 1:
					totalTomato++;
					rottenTomato++;
					queue.offer(new int[]{i,j,2});
					break;
			
				}
			}
		}
		
		if(totalTomato==rottenTomato){
			System.out.println(0);
			return;
		}
		
		bfs();
		
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(tomato[i][j]==0){
					System.out.println(-1);
					return;
				}
			}
		}
		
		int max = Integer.MIN_VALUE;
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				max = Math.max(max, tomato[i][j]);
			}
		}
		
		System.out.println(max-2);
	}//end main 
	
	public static int[][] direction = { {1,0}, {-1,0}, {0,1}, {0,-1} };
	private static void bfs() {
		int[] temp;
		int newX;
		int newY;
		int time;
		
		while(!queue.isEmpty()){
			temp = queue.poll();
			time = temp[2];
			
			for(int d=0;d<4;d++){
				newX = temp[0] + direction[d][0];
				newY = temp[1] + direction[d][1];
				
				if(newX>=0 && newX<N && newY>=0 && newY<M && tomato[newX][newY]==0){
					tomato[newX][newY] = time+1;
					queue.offer(new int[]{newX,newY,time+1});
				}
			}
		}
		
	}

}//end class