[백준 #7576] 토마토

백준 #7576 토마토

백준 #7576

---

문제 설명👩‍🏫

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구해라.

입출력 예

입력
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

출력
8

---

내 코드💻

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

public class Main {
    static int[][] visited;
    static int[][] tomato;
    static int h,w;
    static Queue<int[]> que = new LinkedList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str," ");
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        tomato = new int[h][w];
        visited = new int[h][w];

        for(int i=0;i<h;i++){
            str = br.readLine();
            st = new StringTokenizer(str," ");
            for(int j=0;j<w;j++){
                tomato[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(tomato[i][j] == 1){
                    que.offer(new int[]{i,j});
                }
            }
        }

        int answer = bfs();

        if(answer == -1){
            System.out.println("-1");
        }
        else{
            System.out.println(answer-1);
        }

    }
    static int bfs(){
        int []dicX = {0,0,1,-1};
        int []dicY = {1,-1,0,0};
        int nowX, nowY;
        while(!que.isEmpty()){
            int [] tmp = que.poll();
            for(int i=0;i<4;i++){
                nowX = tmp[0] + dicX[i];
                nowY = tmp[1] + dicY[i];

                if(checking(nowX,nowY) && visited[nowX][nowY]==0 && tomato[nowX][nowY] ==0){
                    que.offer(new int[]{nowX,nowY});
                    visited[nowX][nowY] = 1;
                    tomato[nowX][nowY] = tomato[tmp[0]][tmp[1]]+1;
                }
            }
        }

        int max = 0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(tomato[i][j] == 0){
                    return -1;
                }
                else{
                    max = Math.max(tomato[i][j],max);
                }
            }
        }
        return max;
    }

    static boolean checking(int x, int y){
        return (x >= 0 && x < h && y >= 0 && y < w);
    }

}

---

설명💡

BFS를 사용해서 푸는 문제였다. 상하좌우로 tomato가 0이라면 queue에 추가하면 된다.

---

return (x <= 0 && x > h && y <= 0 && y < w);

실수했던 점은 checking의 return값을 아무생각없이 부등호를 했었다.. (잠왔나봐..)

---

느낀 점 및 궁금한 점🍀

비슷한 문제를 풀다보니 이제 조금 감이 잡히는 거 같기는 하다.