[백준] 7576번 토마토

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q7576.java

토마토가 담겨있는 박스의 상태를 준다. 0은 익지않은 토마토, 1은 익은 토마토, -1은 토마토가 없는
공간을 나타낸다. 익은 토마토의 주변에 익지않은 토마토가 있다면 그 토마토를 하루 뒤에 익게만든다.
이 때, 박스 안의 모든 토마토를 익게 만드는 때까지 걸리는 날짜를 출력하여라. 모든 토마토를 익게만들수
없다면 -1을 출력하여라.

처음 생각

익은 토마토(1)을 기준으로 상 하 좌 우 탐색을하고 또 익은 토마토로 인해 익게된 토마토로 부터 탐색을 해나가면서 진행을 해야하므로 4방향 모두를 살피면서 탐색할 수 있는 BFS 탐색을 이용하여 풀었다.

다음 생각

입력을 받을 때 모든 익은 토마토를 queue에 넣어준 뒤, 탐색을 해나가면서 진행을 하였다.

▶ 익지 않은 토마토만 진행해 나가면 되기때문에 따로 방문 배열을 만들어 줄 필요없이 입력으로 받은 배열의 익지않은 토마토를 1로 만들어주면서 방문 체크를 대신하였다.

다다음 생각

배열이 공백으로 주어지고 최대 1000x1000의 배열이므로 입력의 개수가 많다. Scanner와 BufferedReader의 비교로 좋다고 생각해서 입력을 바꿔서 풀어보았다. 결과는 아래와 같았다.

▶ BufferedReader 사용시 메모리와 시간의 절약이 2배 이상 되는것을 볼 수 있었다. 만약 Scanner를 사용해서 문제풀이시 TLE(시간 초과)가 뜬다면 입력을 확인해보고 입력이 많을 경우 바꿔보는걸 가장 먼저 고려해 보아야한다는걸 볼 수 있었다!

방안

1) Java 풀이

package baekjoon.q1000;
 
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 Q7576 {
    static int n,m;
    static int[][] arr;
    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());
        arr = new int[n][m];
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                // 초기 익은 토마토 queue에 넣어주기
                if(arr[i][j]==1) queue.add(new Pair(i,j));
            }
        }
        System.out.println(solve());
    }
 
    static Queue<Pair> queue = new LinkedList<>();
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static int solve(){
        int result = -1;
        while(!queue.isEmpty()){
            int size = queue.size();
            result++;
            // 모든 익은 토마토에 대해서 하루씩 진행을 해야하기 때문에
            // queue의 size를 미리 받아서 반복문을 통해 딱 그날 익었던 토마토만 탐색
            for(int i=0;i<size;i++){
                Pair t = queue.poll();
                for(int j=0;j<4;j++){
                    int tx = t.x+dir[j][0];
                    int ty = t.y+dir[j][1];
                    if(tx<0 || ty<0 || tx>=n || ty>=m) continue;
                    if(arr[tx][ty]!=0) continue;
                    // 익은 토마토로 만들어주기(방문 표시)
                    arr[tx][ty] = 1;
                    queue.add(new Pair(tx,ty));
                }
            }
        }
        // 익지 않은 토마토가 있나 찾기
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                if(arr[i][j]==0) return -1;
        }
        return result;
    }
 
    static class Pair{
        int x,y;
        Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}