[백준/BOJ/JAVA] 7576 토마토

 

 

토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

보관 후 하루가 지나면, 익은 토마토들의 인접(상하좌우)한 곳에 있는 익지 않은 토마토들은

익은 토마토의 영향을 받아 익게 된다.

토마토가 혼자 저절로 익는 경우는 없다고 가정한다.

철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구하는 문제

만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고,

토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

 

생각보다 어려웠던.. 문제.. 어쩌면 나만 그런 문제.. ?

일(day)수를 구하는 문제이므로 익은 토마토들이 한 번에 큐에 들어가줘야 한다.

 

 

main

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];
    que = new LinkedList<>();
    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) //익은 토마토면 큐에 넣기
                que.add(new int[] {i, j});
        }
    }

    System.out.println(bfs());
}

입력값을 받는 동시에, 익은 토마토는 큐에 넣어준다.

 

 

bfs

public static int bfs() {
    while(!que.isEmpty()) {
        int[] now = que.poll();
        int nowX = now[0];
        int nowY = now[1];

        for(int i=0; i<4; i++) {
            int nextX = nowX + dx[i];
            int nextY = nowY + dy[i];

            //상자 안에 안 익은 토마토
            if(nextX>=0 && nextY>=0 && nextX<N && nextY<M){
                if(box[nextX][nextY]==0){
                    que.add(new int[] {nextX,nextY});
                    box[nextX][nextY] = box[nowX][nowY]+1;
                }
            }
        }
    }

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

            cnt = Math.max(cnt, box[i][j]);
        }
    }

    if(cnt==1) return 0;
    else return cnt-1;
}

인접한 토마토 중 안익은 토마토를 발견하면 큐에 넣어주고 1을 더해준다. now+1일 뒤에 익었다는 의미!!

그리고 인접한 토마토를 모조리 익히고 나면, for문으로 안 익은 토마토가 있는지 체크하고, 최댓값을 구해준다.

최댓값을 구하는 이유 = 제일 나중에 익은 토마토가 얼마나 걸렸는지 구해야함.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ_7576 {
    static final int[] dx= {0,0,1,-1};
    static final int[] dy = {1,-1,0,0};
    static int M, N;
    static int cnt;
    static Queue<int[]> que;
    static int[][] box;
 
    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];
        que = new LinkedList<>();
        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) //익은 토마토면 큐에 넣기
                    que.add(new int[] {i, j});
            }
        }
 
        System.out.println(bfs());
    }
 
    public static int bfs() {
        while(!que.isEmpty()) {
            int[] now = que.poll();
            int nowX = now[0];
            int nowY = now[1];
 
            for(int i=0; i<4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
 
                //상자 안에 안 익은 토마토
                if(nextX>=0 && nextY>=0 && nextX<N && nextY<M){
                    if(box[nextX][nextY]==0){
                        que.add(new int[] {nextX,nextY});
                        box[nextX][nextY] = box[nowX][nowY]+1;
                    }
                }
            }
        }
 
        for(int i=0; i<N; ++i){
            for(int j=0; j<M; j++) {
                if(box[i][j]==0)
                    return -1;
 
                cnt = Math.max(cnt, box[i][j]);
            }
        }
 
        if(cnt==1) return 0;
        else return cnt-1;
    }
}
 

풀고 나니 왜 어려웠지 싶지만... 그것이 코딩