7576. 토마토

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

7576번: 토마토

 

이전의 bfs를 이용하는 문제인 미로탐색과 거의 같지만 한 가지가 다르다고 볼 수 있다.

미로탐색에서는 출발점에서 시작해서 도착점까지의 탐색이다 즉 출발점이 하나다.

토마토 문제는 1로 표현된 익은 토마토의 갯수가 출발점의 갯수이다.

 

그래서 그냥 출발점을 큐에 넣은 미로탐색 문제와는 다르게 

일단 처음에 저장된 배열에서 이미 익어있는 토마토의 갯수를 세고, 그 토마토를 큐에넣는다.

static boolean bfs() {
        int a = 0, b = 0;
        int trigger_n = 0;
        Queue<Integer> q = new LinkedList<Integer>();

        int unripe = 0; // 안익은 토마토 갯수
        for(int i = 0; i < n; i++) { // 토마토 상태확인
            for(int j = 0; j < m; j++) {
                if(arr[i][j] == 1) {
                    q.add(i); q.add(j);
                    visit[i][j] = 1;
                    trigger_n++;
                }
                if(arr[i][j] == 0) unripe++;
            }
        }

그 후 는 미로탐색이랑 똑같이 출발점들(익어 있는 토마토)에서 부터 bfs탐색을 하면된다.