[백준 7576] 토마토

문제설명

문제 풀기
참고 자료

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다.
M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.
단, 2 ≤ M,N ≤ 1,000 이다.
둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다.
하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다.
정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

생각 정리

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

다음과 같은 입력이 주어지면 토마토가 (0,0)과 (3,5)에 위치한 것이다. 토마토는 각자의 위치에서 익어가며, 보관 후 하루가 지날 때마다 인접한 곳에 있는 익지 않은 토마토들은 익어간다.

Q. 이럴 때는 익은 토마토가 있는 두개의 위치 중(0,0과 3,5) 어느 곳에서 탐색을 시작해야할까??

A. 이 문제처럼 탐색을 시작해야하는 위치가 여러개라면, 탐색을 시작해야하는 모든 위치를 queue에 넣고 탐색을 시작한다.

정리된 생각에 대한 논리

 //1인 위치(토마토가 익음) queue에 넣기
        //1인 위치 box에도 표시하기
            //이 때 0이 없으면 처음부터 다 익어있는거임 => 0 출력
            //토마토가 모두 익지 못하는 상황 => bfs 끝났는데 0이 남아있으면 => -1 출력
        //bfs함수호출
        //queue가 비어있지 않을 동안 다음 과정 실행
            //queue에서 꺼낸 위치의 상,하,좌,우를 탐색하면서
            //box의 가로 또는 세로 길이 초과하면 넘어가
            //box[][]가 -1이거나 방문했다면 넘어가
            //그 외에는 
            	//1로 업데이트 (익음) 하고 
                //방문표시하고 
                //queue에 넣고 
                //day 추가해주자 (이전 day에다가)

완성

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


class Position {
    int x, y;

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

public class BOJ7576 {
    static int M, N;
    static int[][] box;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0}; //상우하좌
    static int[] dy = {0, 1, 0, -1};
    static Queue<Position> queue = new LinkedList<>();
    static int 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];
        day = new int[N][M];
        visited = new boolean[N][M];
        boolean flag = true;

        for(int i=0; i<N; i++) {

            String[] newStr = br.readLine().split(" ");
            for(int j=0; j<M; j++) {
				box[i][j] = Integer.parseInt(newStr[j]);

                if(box[i][j] == 1) {
                    visited[i][j] = true;
                    queue.add(new Position(i, j));
                }
                else if(box[i][j] == 0)
                    flag = false;
            }
        }

        if(flag == true) { //0이 없다는 것 : 모든 토마토가 익었음
            System.out.println(0);
        }
        else 
            bfs(0,0);
    }

    static void bfs(int x, int y) {
        int days = 0;
        while(!queue.isEmpty()) {
            Position p = queue.poll();

            for(int i=0; i<4; i++) {

                int nextX = p.x + dx[i];
                int nextY = p.y + dy[i];

                if(nextX<0 || nextY <0 || nextX >= N || nextY>=M) continue;
                else if(visited[nextX][nextY] == true || box[nextX][nextY] == -1) continue;
                else{
                    box[nextX][nextY] = 1;
                    visited[nextX][nextY] = true;
                    queue.add(new Position(nextX, nextY));
                    day[nextX][nextY] = day[p.x][p.y] + 1;
                    days = day[nextX][nextY] ;

                }
            }

        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) { 
                if(box[i][j] == 0){
                    
                    System.out.println(-1);
                    return ;
                }
            }
        }

        System.out.println(days);

    }
}