https://www.acmicpc.net/problem/7576
BFS만 사용하여 계산하는 문제
방향의 유효성을 잘 계산해야함(배열의 경계 , 장애물)

풀이

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

public class Main{
    static int M, N;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int ans = Integer.MIN_VALUE;
    static class Point{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static Queue<Point> q = new LinkedList<>();

    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());
        map = new int[N][M];

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

        bfs();

        if(!check()){
            ans = -1;
        }else{
            ans -= 1;
        }

        System.out.print(ans);
    }

    static void bfs(){
        while(!q.isEmpty()){
            Point t = q.poll();
            int x = t.x;
            int y = t.y;

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

                if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] != 0) {
                    continue;
                }

                map[nx][ny] = map[x][y] + 1;
                q.offer(new Point(nx, ny));
            }
        }
    }

    static boolean check(){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                ans = Math.max(ans, map[i][j]);
                if(map[i][j] == 0){
                    return false;
                }
            }
        }
        return true;
    }
}

풀이

• bfs -> 큐
• dx , dy 로 방향처리
• map[][] 의 값으로 시간을 표현

📌 만약 토마토가 모두 익는 데 3일이 걸렸다면, ans 변수에는 4가 저장된다! (초기 익은 토마토 값 1 + 3일). 따라서 ans -= 1 을 통해 최종적으로 3일이라는 정확한 시간을 출력해야 정답이 되는것!

풀이2

Point 클래스(Dot)에 day 속성을 두어 최종 days를 계산!

🔑 bfs 단계별로 큐에 남아 있는 토마토들은 day 값이 똑같음!! -> 마지막이 모두 익는 데 필요한 최소 일수를 나타내게 됨

BFS를 통해 같은 단계에서 큐에 들어간 토마토들은 day 값이 동일.
BFS는 한 번에 한 단계씩 진행되기 때문에, 큐에 들어간 토마토들은 모두 같은 단계에서 익게 되며, 그 단계에서의 day 값이 적용된다!
이후 다음 단계로 진행할 때 day 값이 1 증가.
👉 즉, 큐가 비게 되면 days에는 가장 오래 걸린 날짜가 저장됨!

static void bfs() {
        while (!queue.isEmpty()) {
            Point current = queue.poll(); // 익은 친구 뺌
            days = current.day;

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

                if (isValid(nx, ny) && box[nx][ny] == 0) { // 배열 경계안이고 익지않은 토마토 일때
                    box[nx][ny] = 1;
                    queue.offer(new Point(nx, ny, days + 1));
                }
            }
        }
    }

public class Song7576_토마토 {
    static int M, N;
    static int[][] box;
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우
    static int[] dy = {0, 0, -1, 1};
    static class Point {
        int x, y, day;
        public Point(int x, int y, int day) {
            this.x = x;
            this.y = y;
            this.day = day;
        }
    }
    static Queue<Point> queue = new LinkedList<>();
    static int days; // 최종값

    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 Point(i, j, 0));
                }
            }
        }

        bfs();

        if (checkAllTomatoes()) {
            System.out.println(days);
        } else {
            System.out.println(-1);
        }
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            Point current = queue.poll(); // 익은 친구 뺌
            days = current.day; // bfs 단계별로 큐에 남아 있는 토마토들은 day 값이 똑같음 -> 마지막이 모두 익는 데 필요한 최소 일수를 나타내게 됨

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

                if (isValid(nx, ny) && box[nx][ny] == 0) {
                    box[nx][ny] = 1;
                    queue.offer(new Point(nx, ny, days + 1));
                }
            }
        }
    }

    //배열 경계 체크
    static boolean isValid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

    static boolean checkAllTomatoes() { // 하나라도 익지 않은 토마토가 있으면 false
        for (int[] row : box) {
            for (int tomato : row) {
                if (tomato == 0) {
                    return false;
                }
            }
        }
        return true;
    }


}