문제 7576번

• 입력 : 가로, 세로, 현재 상자 현황
• 출력 : 토마토가 익는데 걸리는 일수

소스코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class tomato{
    int x;
    int y;
    tomato(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class boj7576 {
    final static int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};
    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());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        box = new int[M][N];
        Queue<tomato> qu = new LinkedList<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
                if(box[i][j] == 1) qu.offer(new tomato(i,j));
            }
        }
        while(!qu.isEmpty()){
            tomato t = qu.poll();
            for(int[] dir : dirs){
                int x = t.x + dir[0];
                int y =  t.y + dir[1];
                if(x>= 0&&y>=0&&x< box.length&&y<box[0].length){
                    if(box[x][y] == 0){
                        qu.offer(new tomato(x,y));
                        box[x][y] = box[t.x][t.y] + 1;
                    }
                }
            }
        }
        int date = 0;
        for (int i = 0; i < M; i++) {
            if(date == -1) break;
            for (int j = 0; j < N; j++) {
                if(box[i][j] ==0){
                    date = -1;
                    break;
                }
                date = Math.max(date, box[i][j]);
            }
        }
        if(date ==1) System.out.println(0);
        else if(date ==-1) System.out.println(-1);
        else System.out.println(date -1);
    }
}

풀이 접근

1. 문제 조건은 한 개 이상의 익은 토마토라는 조건이 있고, 상하좌우로만 영향을 받고, -1이 들어있는 부분은 채울 수 없다.
2. 일단 상하좌우 방향을 계산하기 위한 dirs int[][]배열과 변하지 않는 box배열을 전역변수로 만든다.
3. 문제를 해결하기 위해서 BFS(Breadth First Search)탐색법을 선택 했다.
4. 먼저 현재 상자 현황을 받으면서 익은 토마토가 있는 x,y 좌표를 BFS에서 사용할 Queue에 class형태로 저장한다.
5. !qu.isEmpty()로 반복문 안에 dirs 배열의 반복문을 통해서 익은 토마토 상하좌우에 있는 0을 익은 토마토로 바꿔준다.
6. 총 횟수를 측정하기 위해 5번을 수행하면서 덜 익은 토마토를 익은 토마토로 바꿔줄 때, 처음에 기준이 되었던 익은 토마토 숫자에 1을 더해서 count해 준다.
7. 배열에 덜 익은 토마토가 있는지 for문을 통해 확인한다. date라는 변수에 있다면 -1을 반환하고, 없다면 최대값을 반환한다.
8. date가 -1인 경우 -1을 출력, date가 1인 경우에는 0을 출력, 나머지는 date 값에 -1을 출력한다.

문제핵심

• BFS 탐색방법을 알고 있는지.
• 최대값을 출력하기 위한 방법을 구현할 수 있는지