smooth waters run deep

1d-1c/BOJ

7576_토마토 (JAVA)

yeon_11 2020. 9. 10. 23:28
 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

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을 해줘야한다. 

 

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

'1d-1c > BOJ' 카테고리의 다른 글

2343_기타 레슨 (JAVA)  (0) 2020.09.15
1012_유기농 배추 (JAVA)  (0) 2020.09.11
2667_단지번호붙이기 (JAVA) (C++)  (0) 2020.09.10
2178_미로 탐색 (JAVA) (C++)  (0) 2020.09.10
11047_동전0 (JAVA)  (0) 2020.09.09