JAVA [Algorithm] - 백준 7576 토마토

 

📝문제 설명

 

 

- 익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 없으면 -1

- 하루가 지나면 익지 않은 토마토는 익은 토마토에게 영향을 받아 상하좌우로 익게 된다.

 

입출력 1번을 예시로 변화 과정은 아래와 같다.

---

📢입출력 예시

 

---

✏️문제 풀이

package Baekjoon.Graph.BFS;

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

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

public class Baek7576 {

    static int[][] map;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Queue<Point> queue = new LinkedList<>();
    static int M,N;
    static int day = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

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

        map = new int[N][M];

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

        System.out.println(BFS());
    }

    private static int BFS(){
        while(!queue.isEmpty()){
            Point point = queue.poll();
            int currentX = point.x;
            int currentY = point.y;

            for(int i=0; i<4; i++){
                int newX = currentX + dx[i];
                int newY = currentY + dy[i];

                if(newX >= 0 && newY >= 0 && newX < N && newY < M){
                    if(map[newX][newY] == 0) {
                        queue.offer(new Point(newX, newY));
                        map[newX][newY] = map[currentX][currentY] + 1;
                    }
                }
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j] == 0){
                    return -1;
                }
                day = Math.max(day, map[i][j]);
            }
        }

        if(day == 1){
            return 0;
        }else{
            return day-1;
        }
    }
}

 

BFS 함수 설명

- map을 설정할 때 1(익은 토마토)이 들어오면 미리 큐에 넣어놓는다.

- BFS 함수로 진입하게 되면 1이 있는 x, y좌표를 저장한 후, 상하좌우로 이동시킨다.

- 상하좌우 이동 후, 범위, 조건에 맞게 되면 1이 있던 좌표값보다 +1을 시킨다.

- 그 이유는 다음날 영향을 받아 익게 되는 토마토이며, 익게된 날짜를 의미한다.

 

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j] == 0){
                    return -1;
                }
                day = Math.max(day, map[i][j]);
            }
        }

bfs 함수 내 이 2중반복문의 의미는

- map에 익지 않은 토마토가 전부 있으면 며칠이 지나도 모두 익지 못하기 때문에 -1을 반환

- map 중에 가장 큰 수를 가져온다. 이 의미는 가장 큰 수라는 의미는 익게된 날짜의 마지막 날을 의미한다.

 

 

        if(day == 1){
            return 0;
        }else{
            return day-1;
        }

bfs 함수 내 마지막 조건문의 의미는

- 위 반복문에서 가장 큰 수, 즉 익게된 마지막 날짜가 1이게 되면 이미 모두 익은 상태이기 때문에 0을 출력하고

- 아니면 -1값을 하여 출력한다.

예제 1번을 실제로 출력해보면 map에 저장되는 값은 이렇게 저장되기 때문에 -1을 해줘야한다.

---

💡새로 알게된 점

2차원 배열에서 상하좌우로 영향을 받는다 == BFS 및 DFS 문제

최소 날짜를 구하고 싶다 == BFS 문제

 

이제 슬슬 BFS, DFS를 구별 할 수 있을 것 같다.

---