백준 7576

문제

입력 / 출력

예제

풀이

익은 토마토(1)의 상하좌우를 확인해야하기 때문에 dx,dy 기법을 사용한다.
dx/dy
현재 위치에서 상하좌우의 인덱스를 만들어내는 방법.
좌우는 열의 좌표가 +1되거나 -1 됩니다. 상하는 행의 좌표가 +1 되거나, -1이 됩니다.

코드 설명
익은 토마토 (값이 1) 배열의 좌표를 queue에 저장한다.
익지 않은 토마토 (값이 0)가 발견되면 count++

익은 토마토(queue)와 익지않은 토마토(count) 가 값이 존재한다면,
익은 토마토의 좌표에서 dx/dy 로 4방 탐색을 한다.

탐색 과정에서 0이 발견되면 1로 값을 바꾸고, 현재 위치를 queue에 추가
익지않은 토마토는 -1
그리고 출력 값 days++

queue가 빈 값이 되거나,count가 0이되면 탐색을 멈춘다.
익지않은 토마토(count)가 0이면 day의 값을 출력
아니라면 -1 출력

코드

import java.util.*;
import java.io.*;
class Main{
    static int[][] tomato;
    static int N,M;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    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()); //세로

        tomato = new int[N][M]; //박스에 들어있는 토마토 이중 배열(크기는 N,M)

        int count = 0; // 안 익은 토마토 개수
        int days = 0; // 완료되는 기간

        Queue<int[]> queue = new LinkedList<>(); //탐색 후 토마토가 존재하는 인덱스를 저장할 큐

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                tomato[i][j] = Integer.parseInt(st.nextToken()); // 토마토 1은 익은 토마토 , 0은 덜 익은 토마토 ,-1은 빈 칸
                if(tomato[i][j]==1){
                    queue.add(new int[]{i,j}); // 익은 토마토가 들어있는 인덱스 저장
                }else if(tomato[i][j]==0){
                    count++;
                }
            }
        }


        while (count > 0 && !queue.isEmpty()){
            for(int i= queue.size();i>0;i--){
                int[] cur = queue.poll();

                for (int j =0;j<4;j++){
                    int ny = cur[0] + dy[j];
                    int nx = cur[1] + dx[j];
                    if(ny < 0 || nx < 0||ny>=N||nx>=M|| tomato[ny][nx] != 0){
                        continue;
                    }
                    count--; //안 익은 토마토 개수를 줄임
                    tomato[ny][nx] = 1; // 익은 토마토가 됨
                    queue.add(new int[]{ny,nx}); // 똑같이 인덱스 큐에 추가
                }
            }
            days++;
        }
        if(count == 0){ // 출력
            System.out.println(days);
        }else System.out.println(-1);

    }
}