백준 7576번 : 토마토 풀이(Java) - BFS

www.acmicpc.net/problem/7576

7576번: 토마토

 

얼마 전에 풀었던 문제인데 다시 풀게 되었다.

 

Solution

이 문제는 BFS를 구현할 줄 안다면 크게 어렵지 않은데, 주의할 점은,

• 이미 익어있는 토마토(즉, 시작점) 가 처음에 여러 개 있을 수 있다.
• 토마토가 몇 초 대에 익는지 기록한다.

이다. 즉, 1번의 경우 여러 토마토가 한 번에 큐에 담겨서 같이 순차적으로 진행될 수 있도록 해야한다는 의미이다.

2번의 경우는, 큐에 담을 때 토마토가 몇 초 대에 익는지 기록하고 나면, 그 토마토에 의해서 익을 다음 토마토들은 이전 토마토가 익은 시간 + 1 이 담기면 된다는 것이다. ( 2초 대에 익은 토마토가 3초 대에 상,하의 토마토를 익힘 )

 

한 번 풀어봤던 문제라 빠르게 풀었다.

실행 시간을 줄인 것은, 입력 받을 때 익혀야 되는 토마토의 수, 즉 0인 것들의 갯수를 세어서 bfs를 돌고 난 이후에 체크해줘서 2차원 반복을 피할 수 있었다. 입력이 작아서 크게 소용있진 않았지만,,

 

Source Code

import java.io.*;
import java.util.*;

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int width, height, result, shouldRipeCount;
    private static int[][] map;
    private static ArrayList<Node> tomatoes;
    private static boolean[][] visited;
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,-1,1};


    private static class Node {
        int x;
        int y;
        int depth;

        public Node(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }

    private static void input() throws IOException {
        StringTokenizer wh = new StringTokenizer(bufferedReader.readLine());
        width = Integer.parseInt(wh.nextToken());
        height = Integer.parseInt(wh.nextToken());
        map = new int[height][width];
        visited = new boolean[height][width];
        tomatoes = new ArrayList<>();
        for(int i = 0 ; i < height; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0 ; j < width; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) {
                    tomatoes.add(new Node(i,j, 0)); // 이미 익은 토마토들을 담아주고,
                    visited[i][j] = true; // 방문 처리도 해준다.
                } else if(map[i][j] == 0) {
                    shouldRipeCount++; // 익혀야 하는 토마토 갯수
                }
            }
        }
    }

    private static boolean bfs() {
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.addAll(tomatoes); // 초기에 익은 토마토들을 먼저 담는다.
        int ripeCount = 0; // BFS로 인해 익을 토마토의 갯수를 담는다.
        while (!queue.isEmpty()) {
            Node s = queue.poll();
            int sx = s.x;
            int sy = s.y;
            int sd = s.depth; // 토마토가 sd 초에 익었다는 것을 나타낸다.
            result = sd; // BFS 가 끝날 때,마지막에 익은 토마토는 sd초에 익을 것이므로 계속 대입해준다.
            for(int i = 0 ; i < 4; i++) {
                int nx = sx + dx[i];
                int ny = sy + dy[i];
                if(nx < 0 || ny < 0 || nx >= height || ny >= width) continue;
                if(visited[nx][ny]) continue;
                if(map[nx][ny] == 0) {
                    map[nx][ny] = 1;
                    ripeCount++;
                    visited[nx][ny] = true;
                    queue.add(new Node(nx, ny, sd + 1));
                }
            }
        }
        if(ripeCount == shouldRipeCount) { // 익힌 갯수 = 익혀야 할 갯수라면 true
            return true;
        } else return false;
    }

    private static void solve() throws IOException {
        if(bfs()) {
            System.out.println(result);
        } else {
            System.out.println(-1);
        }

    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}