[BFS / DFS] [백준 / 7576 ] 골드5 - 토마토 (java/자바)

문제

풀이 생각

BFS 시작

• 토마토는 동시에 익는다. 그렇기에 토마토들을 동시에 BFS의 큐에 넣는다.
  이때부터 한칸씩 넘어갈때마다 넘어간 횟수를 세어야 한다.

BFS 좌표 이동 조건

• 토마토의 상함은 상하좌우로 이동한다. 이때 이동 가능 조건이 있다.
  • 1. 매트릭스 내부에 있어야 한다.
  • 2. 다음 이동 좌표값은 -1이 아니어야 한다.
  • 3. 방문한 적 없는 좌표여야 한다.

날짜 출력하기

• 최대 날짜를 구하는 방법 2가지

  • 1. 좌표마다 첫 토마토로부터 이동한 횟수를 가지고 있는 배열을 만든다. BFS가 끝난 후, 이 배열로부터 최댓값을 찾아서 출력한다.
  • 2. BFS 실행 도중, 최댓값을 계속 갱신한다. BFS가 끝나면 최댓값을 반환하고 출력한다. ( 저는 이 방법으로 풀었습니다.)

• 토마토가 모두 익지 못하는 상황은 -1 출력하기

  • 토마토가 익으면 0을 1로 만들어 익게 합니다. BFS 알고리즘 종료 후, 만약 2차원 배열에 0이 남아 있다면 -1을 출력하고 종료합니다.

성공 코드

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

public class Main{
    static int M, N;
    static int[][] matrix;
    static boolean[][] visited;

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

    static int maxDay = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(r.readLine());
        M = Integer.parseInt(st.nextToken()); //가로
        N = Integer.parseInt(st.nextToken()); //세로

        matrix = new int[N][M];
        visited = new boolean[N][M];
        List<Point> rememberStartPoints = new ArrayList<>();

        // 초기화 부분
        for (int i = 0; i < N; i++) {
            StringTokenizer st1 = new StringTokenizer(r.readLine());
            for (int j = 0; j < M; j++) {
                int num = Integer.parseInt(st1.nextToken());
                if (num == 1) {
                    rememberStartPoints.add(new Point(i, j, 0));
                }
                matrix[i][j] = num;
            }

        }
        // 알고리즘 실행
        bfs(rememberStartPoints);
        

        // 출력부분
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == 0) {
                    System.out.println("-1");
                    return;
                }
            }
        }
        System.out.println(maxDay);

    }
    static void bfs(List<Point> rememberStartPoints){
        Queue<Point> q = new LinkedList<>();

        for(int i=0; i<rememberStartPoints.size();i++){
            Point getPoint = rememberStartPoints.get(i);
            visited[getPoint.y][getPoint.x] = true;
            q.add(getPoint);
        }
        while(!q.isEmpty()){
            Point currentPoint = q.poll();
            for(int i=0; i<4; i++){
                int nextY = currentPoint.y + dy[i];
                int nextX = currentPoint.x + dx[i];

                if(!( 0<=nextY && nextY <N && 0<= nextX && nextX <M)) continue;
                if(visited[nextY][nextX]) continue;
                if(matrix[nextY][nextX] == -1) continue;

                q.add(new Point(nextY,nextX, currentPoint.day+1));
                visited[nextY][nextX] =true;
                matrix[nextY][nextX] = 1; // 익게 만듦

                maxDay = Math.max(maxDay, currentPoint.day+1);
            }
        }
    }
    static class Point {
        int y, x, day;

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

}

BFS 알고리즘인 이유

동시성 문제

문제에서는 익은 토마토들이 인접한 익지 않은 토마토를 동시에 하루가 지날 때마다 익게 만든다는 조건이 있습니다. BFS는 레벨 별로 탐색을 진행하기 때문에, 하루가 지날 때마다 동시에 발생할 수 있는 이러한 변화를 모델링하는 데 적합합니다. 즉, 하루가 지나면서 일어나는 모든 변화를 한 단계의 탐색으로 처리할 수 있습니다. 이렇게 단계별로 탐색할때는 BFS를 사용합니다. 그래서 깊이로 탐색하는 DFS보다는 넓이로 탐색하는 BFS 입니다.