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 |