[백준 7576,Java] 토마토

문제

www.acmicpc.net/problem/7576

7576번: 토마토

 

풀이

 현재 토마토의 위치를 기준으로 북, 동, 남, 서쪽을 차례로 탐색한 후 익지 않은 토마토가 있으면 익은 토마토로 만든다. 북동남서 방향으로 동시에 확산 되는 것이므로 bfs를 통해 탐색을 한다. 

 

 처음 입력을 받을 때 값이 1인 좌표를 queue에 add한다. 이 queue가 빌 때까지 bfs로 탐색을 한다. 익지 않은 토마토가 있을 때 map을 업데이트 하는데, 업데이트 하는 값의 의미는 익은 순서가 된다. 즉, 맨 처음 queue에 add되는 요소는 map[r][c] =1인 요소로 맨 처음 익은 토마토를 의미한다. 따라서 출력을 할때는 이 순서에서 -1을  해줘야 익는데 까지 걸리는 시간이 된다. 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Tomato{
    int x;
    int y;
    Tomato(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main {
    public static int N;
    public static int M;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dx = {-1,0,1,0};
    public static int[] dy= {0,1,0,-1};
    public static Queue<Tomato> queue;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];
        queue = new LinkedList<>();

        for(int r = 0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<M; c++){
                int value = Integer.parseInt(st.nextToken());
                if(value==1){
                    queue.add(new Tomato(r, c));
                }
                map[r][c] = value;
            }
        }

        bfs();
        int result = findMinimumDay();
        bw.write(String.valueOf(result));
        bw.flush();
    }

    public static void bfs(){
        while (!queue.isEmpty()){
            Tomato currentTomato = queue.poll();

            for(int d = 0; d<4; d++){
                int nx = currentTomato.x + dx[d];
                int ny = currentTomato.y + dy[d];
                int nd = map[currentTomato.x][currentTomato.y] +1;

                if(nx >=0 && ny >=0 && nx<N && ny<M){
                    if(map[nx][ny]==0){
                        map[nx][ny] = nd;
                        queue.add(new Tomato(nx, ny));
                    }
                }

            }
        }
    }

    public static int findMinimumDay(){
        int result = -1;

        for(int r= 0; r<N; r++){
            for(int c= 0; c<M ; c++){
                if(map[r][c]==0){
                    return -1;
                }
                else{
                    result = Math.max(result, map[r][c]);
                }
            }
        }
        return result-1;
    }
}