[백준7576] 토마토[java]

---

토마토가 익어가면서 옆으로 퍼지는 것이므로 bfs를 이용해서 풀었다!!

요즘 풀었던 dfs와 bfs처럼 상하좌우를 살펴야 하므로 미리 좌표를 선언해뒀다.

그리고 요번에는 띄어쓰기가 있는 문장을 받았으므로 BufferedReader를 사용해줬다.

bfs메소드에서는 각각의 x,y를 큐에 넣고 빼줬다. 그러는 과정에서 토마토가 다 익은 날짜를 구해야 하므로 이전 값보다 +1씩 해줬다.

 

1. 입력받은 수들을 이차원 배열로 만들어준다

2. 1토마토가 있는 좌표를 큐에 넣는다.

3. 토마토 좌표 주위로 0토마토가 있으면 1토마토의 값을 +1한채로 더해주고 0토마토의 좌표를 큐에 넣어준다.

4. 마지막에 전체에서 0토마토가 남아있으면 -1을 출력하고 바로 return을 해준다. 아니면 이중배열의 원소들중 최댓값-1을 한 값을 출력한다.

 

코드

package baekjoon;

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

public class tomato {
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int n,m;
    static int[][] tomato;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        tomato = new int[m][n];
        for(int i = 0; i<m;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<n;j++){
                tomato[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        bfs();
    }

    private static void bfs() {
        Queue<Integer> queue_x = new LinkedList<Integer>();
        Queue<Integer> queue_y = new LinkedList<Integer>();

        for(int i = 0; i<m;i++){
            for(int j = 0; j<n;j++){
                if(tomato[i][j] == 1){
                    queue_x.add(i);
                    queue_y.add(j);
                }
            }
        }
        while(!queue_x.isEmpty()){
            int x = queue_x.poll();
            int y = queue_y.poll();

            for(int i = 0; i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx >= 0 && ny>=0 && nx<m && ny<n){
                    if(tomato[nx][ny]==0){
                        tomato[nx][ny] = tomato[x][y]+1;
                        queue_x.add(nx);
                        queue_y.add(ny);
                    }
                }
            }
        }
        int max = 0;
        for(int i = 0; i<m;i++){
            for(int j = 0; j<n;j++){
                if(tomato[i][j] == 0){
                    System.out.println(-1);
                    return;
                }
                max = Math.max(max, tomato[i][j]);
            }
        }
        System.out.println(max-1);
    }
}