백준 7576 토마토 자바

7576 토마토 문제 보러가기

7576번: 토마토

문제 설명

자바 코드

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

public class Main {
    static int n, m;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int[][] input;
    static int zeroCount=0;
    static int day=-1;
    static Queue<Point> queue=new LinkedList<Point>();
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer strToken=new StringTokenizer(br.readLine()," ");
        n=Integer.parseInt(strToken.nextToken());
        m=Integer.parseInt(strToken.nextToken());
        input=new int[n][m];
        for(int i=0;i<m;i++){
            String[] line = br.readLine().split(" ");
            for(int j=0;j<n;j++){
                int no=Integer.parseInt(line[j]);
                if(no==0) zeroCount++;
                if(no==1) queue.add(new Point(j,i,0));
                input[j][i]=no;
            }
        }
        bfs();
        System.out.println(day);
    }
    static void bfs(){
        while (!queue.isEmpty()){
            Point point = queue.poll();
            if(zeroCount<=0){
                day=Integer.max(day,point.day);
            }
            for (int i = 0; i < dx.length; i++) {
                int nextX = point.x+dx[i];
                int nextY = point.y+dy[i];
                if (nextX < 0 || nextY < 0 || nextX > (n-1) || nextY > (m-1)) continue;
                if (input[nextX][nextY] == 0) { // 토마토라면
                    input[nextX][nextY]=1;//토마토를 익히고
                    zeroCount--;
                    queue.add(new Point(nextX,nextY,point.day+1));
                }

            }

        }
    }
    static class Point{
        int x,  y;
        int day=0;
        Point(int x,int y){
            this.x=x;
            this.y=y;
        }
        Point(int x,int y,int day){
          this(x,y);
          this.day=day;
        }
    }
}

문제 풀이

이번 문제는 bfs+동적프로그래밍으로 구현하였습니다.

넓이 탐색하여 익은 토마토 상하좌우를 파악하고 안익은 토마토라면 토마토를 익히고 기존에 익어있던 토마토 날 +1을하여 가지고 있다가 모든 토마토가 익으면 결과값을 도출 하였습니다.

감사합니다.