[백준/7576] 토마토 - JAVA

📌 문제

알고리즘 분류 : 그래프
난이도 : 골드5
출처 : 백준 - 토마토

🦧 문제 풀이 접근

매일 조금씩 확장되어가는 형태기 때문에 BFS를 사용했다.
이때 tomatoCnt변수에 -1과 1로 변한 0의 갯수를 카운트해준 후 토마토가 모두 익지 못하는 상황을 찾는다.

💻 code

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int tomatoCnt = 0;
        int finalTomatoDate=0;
        Queue<Tomato> queue = new LinkedList<>();
        int[][] farm = new int[N][M];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                int n = Integer.parseInt(st.nextToken());
                if(n==0)
                    farm[i][j] = 0;
                else if(n==1) {
                    farm[i][j] = 1;
                    queue.add(new Tomato(i,j,0));
                    tomatoCnt++;
                }
                else {
                    farm[i][j] = -1;
                    tomatoCnt++;
                }
            }
        }
        while(!queue.isEmpty()) {
            Tomato tomato = queue.poll();
            finalTomatoDate = tomato.date;
            if(0<tomato.i) {
                if(farm[tomato.i-1][tomato.j]==0) {
                    tomatoCnt++;
                    queue.add(new Tomato(tomato.i-1,tomato.j,tomato.date+1));
                    farm[tomato.i-1][tomato.j]=1;
                }
            }
            if(0<tomato.j) {
                if(farm[tomato.i][tomato.j-1]==0) {
                    tomatoCnt++;
                    queue.add(new Tomato(tomato.i,tomato.j-1,tomato.date+1));
                    farm[tomato.i][tomato.j-1]=1;
                }
            }
            if(tomato.i<N-1) {
                if(farm[tomato.i+1][tomato.j]==0) {
                    tomatoCnt++;
                    queue.add(new Tomato(tomato.i+1,tomato.j,tomato.date+1));
                    farm[tomato.i+1][tomato.j]=1;
                }
            }
            if(tomato.j<M-1) {
                if(farm[tomato.i][tomato.j+1]==0) {
                    tomatoCnt++;
                    queue.add(new Tomato(tomato.i,tomato.j+1,tomato.date+1));
                    farm[tomato.i][tomato.j+1]=1;
                }
            }
        }
        if(tomatoCnt == M*N)
            System.out.println(finalTomatoDate);
        else
            System.out.println(-1);

    }
}
class Tomato {
    int i;
    int j;
    int date;
    Tomato(int i, int j, int date) {
        this.i = i;
        this.j = j;
        this.date = date;
    }
}

🥇 결과

🎓 느낀점

BFS, DFS문제를 풀때는 어떤 알고리즘을 써야하는지 먼저 파악하는것이 중요하다.