7576_토마토 (JAVA)

7576번: 토마토

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static int M, N;
	static int dx[]={-1,1,0,0};
	static int dy[]={0,0,-1,1};
	static int[][] box;
	
	static class XY{
		int x, y;
		public XY(int x, int y){
			this.x = x; this.y = y;
		}
	}
	
	public static void main (String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt(); N = sc.nextInt();
		box = new int[N][M];
		
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				box[i][j] = sc.nextInt();
			}
		}
		
		BFS();
		
		int max = 0;
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				if(box[i][j]==0){
					System.out.println(-1);
					return;
				}
				else{
					if(max<box[i][j]) max = box[i][j];
				}
			}
		}
		System.out.println(max-1);
		return;
	}
	
	public static void BFS(){
		Queue<XY> q = new LinkedList<XY>();
		
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				if(box[i][j]==1){
					q.offer(new XY(i,j));
				}
			}
		}
		
		
		while(!q.isEmpty()){
			
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();
			
			for(int k=0; k<4; k++){
				int xx = x+dx[k];
				int yy = y+dy[k];
				
				if(xx>=0&&xx<N && yy>=0&&yy<M){
					if(box[xx][yy]==0){
						box[xx][yy] = box[x][y]+1;
						q.offer(new XY(xx,yy));
					}
				}
			}
		}
	}
}

 

입력받은 M,N을 행/열을 반대로 생각해서 계속 런타임에러로 맘고생..

진짜 헷갈려 죽는줄알았다ㅠㅠ

 

[문제 풀이 생각 과정]

1. '최소' 일수를 알아야하기 때문에 BFS 이용!

2. 1인 곳에서 동시다발적으로 날짜를 세어야하기때문에 - 먼저 1인 위치를 모두 큐에 넣고 시작한다.

    [x][y]위치의 왼쪽,오른쪽,위쪽,아래쪽 모두를 확인하면, 토마토가 익는 1일이랑 같은 의미이다.

    그러므로 box[xx][yy]=box[x][y]+1; 해준다.

3. +1을 해준 위의 식은 처음 시작을 1로부터 하기때문에, 총 걸리는 일수는 -1을 해줘야한다. 

 

**런타임에러는 무조건 배열 범위/조건 문제 라고 생각하고 큰눈뜨고 살펴보기!!!!!