백준 7576번 - 토마토 / Java

문제

https://www.acmicpc.net/problem/7576

7576번: 토마토

BFS탐색 문제이다. 문제에 "최소 날짜"를 출력하라고 하는데 "최소"를 구하기 위해서는 BFS로 탐색해야 한다 DFS로는 구할 수 없다

토마토가 익으면 주변의 토마토를 모두 익게하므로 점점 익는 범위가 많아진다. 이 부분을 유의해서 동시적으로 구현해줘야 한다

 

알고리즘

1. 입력받을 때 익어있는 토마토를 미리 큐에 넣어놓는다

2. q에 들어있는 개수만큼만 탐색을 하고 날짜를 세준다. 구분 없이 탐색을 하면 날짜를 셀 수 없기 때문

3. 큐가 빌 때까지 2를 반복하고 답을 출력한다

소스코드

/*
 * BOJ7576
 * 2020.01.23
 * Hyeonseong
 */
import java.util.*;
public class BOJ7576
{
    public static void main(String[] args) 
    {
        Solution s = new Solution();
    }
}
class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}
class Solution{
    int m; // 가로
    int n; // 세로
    int answer;
    int map[][];
    boolean visit[][];
    Queue<Node> ripe;
    public Solution() {
        Scanner scan = new Scanner(System.in);
        m = scan.nextInt();
        n = scan.nextInt();
        answer = 0;
        map = new int[n][m];
        visit = new boolean[n][m];
        ripe = new LinkedList<Node>();
        for(int i=0;i<n;i++) {
            map[i] = new int[m];
            visit[i] = new boolean[m];
            for(int j=0;j<m;j++) {
                map[i][j] = scan.nextInt();
                if(map[i][j]==1) {
                    ripe.add(new Node(i,j));
                }
            }
        }
        while(!ripe.isEmpty()) { // 토마토가 다 익을때 까지
            bfs(ripe.size());
            answer++;
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(map[i][j]==0) { // 안익은게 있으면 -1
                    System.out.println("-1");
                    System.exit(0);
                }
            }
        }
        System.out.println(answer-1);
    }
    public void bfs(int num) { //익은 토마토의 수만큼 돌린다 
        int dx[] = {-1,0,1,0};
        int dy[] = {0,1,0,-1};
        while(num-->0) {
            Node t = ripe.poll();
            for(int i=0;i<4;i++) {
                int di = t.x+dx[i];
                int dj = t.y+dy[i];
                if(di>=0 && dj>=0 && di<n && dj<m) {
                    if(!visit[di][dj] && map[di][dj]==0) {
                        ripe.offer(new Node(di,dj)); // 익은 토마토 추가
                        visit[di][dj] = true;
                        map[di][dj] = 1;
                    }
                }
            }
        }
    }
}