[백준 7576번] 토마토 - JAVA

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

7576번: 토마토

풀이

 

사용한 알고리즘 : BFS

 

풀이전략

기존 BFS에서 하나의 조건을 추가해야하는 문제이다.

 

기본적인 BFS 문제에서는 하나의 지점에서 조건이 충족되는 인접한 지점들을 방문하여 부분 집합의 개수를

구하는 것이 목표였다. 또한 전파가 걸리는 시간을 질문하지 않았다.

 

하지만 위 문제에서는 하나의 지점이 아닌 여러개의 지점에서 동시에 BFS 탐색이 진행되어야 한다.

그래야만 하루 간 토마토가 익는 정도를 파악할 수 있기 때문이다.

 

이를 구현하기 위해 BFS 탐색 중 반복문을 하나 더 삽입하였다.해당 반복문은

현재 인접한 익지 않은 토마토를 익게할 수 있는 토마토의 개수만큼을 반복한다.

 

위에서 설명한 반복문의 한 싸이클은 하루를 나타내며, 이를 통해 하루가 지났을 때, 토마토의 상태 변화를

인지할 수 있다.

 

BFS 탐색이 끝나면 토마토의 모든 상태를 확인하고,만약 익지않은 토마토가 하나라도 있는 경우 -1을 출력,

익지 않은 토마토가 없다면 BFS 탐색 중 반복문을 통해 구한 날짜 카운트를 출력한다.

 

제출코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int M,N;
    static int graph[][];
    static int dx[] = {-1,0,1,0};
    static int dy[] = {0,1,0,-1};

    static boolean visited[][];
    static int dayCount=0;
    static class Node{
        int x;
        int y;

        public Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    static void bfs(ArrayList<Node> nodes){
        Queue<Node> q = new LinkedList<>();
        for(Node node:nodes){
            q.offer(node);
        }

        while(!q.isEmpty()){
            int roundQ = q.size();
            for(int k=0;k<roundQ;++k){
                Node nowNode = q.poll();

                for(int i=0;i<4;++i){
                    int mx = nowNode.x+dx[i];
                    int my = nowNode.y+dy[i];

                    if(mx>=0 && mx<N && my>=0 && my<M){
                        if(graph[mx][my]==0){
                            graph[mx][my]=1;
                            q.offer(new Node(mx,my));
                        }
                    }
                }
            }
            ++dayCount;
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        graph = new int[N][M];
        visited = new boolean[N][M];

        ArrayList<Node> startNodes = new ArrayList<>();
        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;++j){
                graph[i][j]=Integer.parseInt(st.nextToken());
                if(graph[i][j]==1) startNodes.add(new Node(i,j));
            }
        }

        bfs(startNodes);

        boolean allClear=true;
        outter :for(int i=0;i<N;++i){
            for(int j=0;j<M;++j){
                if(graph[i][j]==0){
                    allClear=false;
                    break outter;
                }
            }
        }
        if(allClear) bw.write(dayCount-1+"\n");
        else bw.write(-1+"\n");
        bw.flush();
        bw.close();
    }
}