[백준 / Java] 7576번 토마토

사용한 알고리즘 (BFS)

BFS

https://cobi-98.tistory.com/36

[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해

 

🔒 7576번 토마토

✔ 문제 설명

🚩 요구사항 분석

• 토마토 생성자 추가 (VO)
• int [ ][ ] M, N 상자(box) 생성
• 상하좌우로 이동할 수 있는 배열(dx, dy) 생성
• 익은 토마토 queue에 추가
• 큐가 빌 때까지 반복
  
  • 이동할수 있는 경로(상자에 벗어나지 않는 경우)
  • 상하좌우를 확인해 익지 않은 토마토라면 해당 토마토를 익게 만든다.
  • 그 토마토의 위치를 queue 추가
  • 날짜 ++;
• queue가 다 비었을 때 안 익은 토마토가 있다면 -1

 

 

🔑 문제풀이

요구사항을 분석한 대로 queue에 익은 토마토를 넣는다.  

queue에 담겨져있는 현재 익은 토마토의 해당 위치를 꺼내서  상하좌우를 체크한다.

 

아직 익지 않은 토마토가 있다면,

토마토의 위치를 큐에 추가

토마토 날짜(day)  + 1 증가

 

큐가 비어져서 상자의 (토마토를 다 익게 만들었다면)

토마토상자 전체를 다시 돌면서 익지 않은 토마토가 있다면 -1을 출력, 없다면 day 날짜를 출력

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 Main {
    public static int N;
    public static int M;
    public static int[][] box;

    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};

    public static Queue<tomato> queue = new LinkedList<tomato>();

    static class tomato{
        int x;
        int y;
        int day;

        public tomato(int x, int y, int day){
            this.x = x;
            this.y = y;
            this.day = day;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        box = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
                if(box[i][j] == 1){
                    queue.offer(new tomato(i,j,0));
                }

            }
        }

        bfs();
    }

    public static void bfs() {
        int day = 0;

        while(!queue.isEmpty()) {
            tomato t = queue.poll();
            day = t.day;

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

                if(0 <= nx && nx <N && 0<= ny && ny <M) {
                    if(box[nx][ny] == 0) {
                        box[nx][ny] = 1;
                        queue.add(new tomato(nx, ny, day+1));
                    }
                }
            }
        }

        if(checkTomato()){
            System.out.println(day);
        } else{
            System.out.println(-1);
        }

    }

    static boolean checkTomato() {
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(box[i][j] == 0)
                    return false;
                // 덜 익은 토마토가 있다면
            }
        }
        return true;
    }

}