[백준 BFS] 7576번: 토마토 (Java)

https://www.acmicpc.net/problem/7576

백준 7576번 토마토

 

며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성 

=> BFS 유형임을 catch해야 한다.

 

BFS 유형 중 시작점이 여러 개인 유형이다.

토마토가 익어있는 곳이 한 군데가 아니라 여러 군데일 수 있다.

시작점들을 모두 큐에 넣고 시작하면 해결이 가능하다 : 가장 빠르게 BFS를 완료하는 곳이 정답이기 때문

 

package main;

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {

        //배열 선언
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstL = br.readLine().split(" ");
        int M = Integer.parseInt(firstL[0]);
        int N = Integer.parseInt(firstL[1]);

        int[][] board = new int[N][M];


        Queue<Pair> Q = new ArrayDeque<>();

        //배열 값 채우기
        for(int i=0; i<N; i++){
            String inputL = br.readLine();
            StringTokenizer st = new StringTokenizer(inputL);
            for(int j=0; j<M; j++){
                int input = Integer.parseInt(st.nextToken());
                board[i][j] = input;

                //입력으로 익은 토마토인 1을 받았을 때 Q에 넣는다.
                if(input==1) {
                    Q.add(new Pair(j, i, 0));
                    board[i][j] = 2; //방문한 곳들은 2로 표기
                }
            }
        }

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

        //모든 토마토가 익어있다면 BFS를 수행하고도, 맨 마지막 결과에서 0이 출력된다.
        int day = 0;

        //BFS
        while(!Q.isEmpty()){

            Pair remove = Q.poll();
            day = remove.day; //결과로 제출할 day를 반영

            //큐에서 제거한 좌표와 인접한 좌표
            for(int i=0; i<4; i++){
                int nx = remove.x + dx[i];
                int ny = remove.y + dy[i];

                //유효성 검증
                if(nx<0 || ny<0 || nx==M || ny==N || board[ny][nx]!=0) continue;

                Pair pair = new Pair(nx, ny, remove.day+1);
                Q.add(pair);
                board[ny][nx] = 2;
            }
        }


        //BFS가 종료되었을 때 board에 0이 남아있거나 : return -1
        for(int i=0; i<N; i++) {
            for (int j = 0; j < M; j++) {
                if(board[i][j]==0) {
                    System.out.println(-1);
                    return;
                }
            }
        }
        //BFS가 종료되었을 때 board에 0이 남아있지 않거나 (-1, 2로만 구성) : return day
        System.out.println(day);
    }

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

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

 

이미 방문한 공간은 board 배열 상에서 2라는 값을 입력해주었다

BFS를 수행하는 곳에서 좌표 유효성 검증은 

if(nx<0 || ny<0 || nx==M || ny==N || board[ny][nx]!=0) continue;

위와 같이 하였는데, board[ny][nx]!=0으로 설정하여서 토마토가 존재하지 않는 -1이나 이미 익어있는 0, 그리고 이미 지나온 2를 만나면

다음 nx ny 좌표로 이동하도록 설계하였다.

 

BFS에서 요구하는 답이 매번 있는데(distance, day ..)

결과로 제출할 답을 Pair 클래스의 필드로 넣어서 코드를 짜면 답을 도출하기 쉬워진다.

 

처음 배열 입력 시 익은 토마토를 나타내는 1은 바로 Q에 넣어주었는데,

이렇게 바로 넣지 않으면 익은 토마토를 확인하는 for문을 다시 돌려야 해서 실행 시간이 더 걸릴 것이라 생각하여

처음 배열 입력에서 1이 들어온 값은 바로 Q로 넣어주었다.

 

*Point

BFS를 수행할 때 큐에 쌓이게 되는 순서는 반드시 거리 순이다.