[백준] 토마토 - 7576

문제설명

www.acmicpc.net/problem/7576

7576번: 토마토

 

기본아이디어

정말 정석적인 BFS 탐색 문제입니다. 익은 토마토를 찾아서 주변 네방향으로 안익은 토마토를 찾으면 익은 상태로 만들고 다음에 새로 익은 토마토 기준으로 반복하면 된다.

 

구현코드

 public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(input.readLine());
 
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        map = new int[N][];
        int r = 0;
        int c = 0;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(input.readLine());
            int[] temp = new int[M];
            for(int j = 0; j < M; j++) {
                temp[j] = Integer.parseInt(st.nextToken());
            }
            map[i] = temp;
        }
        System.out.println(bfs());
    }
    static int N,M;
    static int[][] map;
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int bfs(){
        int result = -1;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(map[i][j] == 1)
                    queue.add(new int[]{i,j});
            }
        }
 
        while (!queue.isEmpty()){
            int size = queue.size();
            result++;
            for(int i = 0; i < size; i++) {
                int[] loc = queue.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = loc[0] + dr[d];
                    int nc = loc[1] + dc[d];
                    if (isIn(nr, nc) && map[nr][nc] == 0) {
                        map[nr][nc] = 1;
                        queue.add(new int[]{nr, nc});
                    }
                }
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(map[i][j] == 0)
                    return -1;
            }
        }
        return result;
    }
    static boolean isIn(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < M;
    }
 
 

 

정리, 기억할 내용

1. BFS 탐색!!