[백준 7576 : JAVA] 토마토 / BFS

개요

 

BFS와 DFS는 탐색 알고리즘이다.

둘 중 어떤 알고리즘을 선택할 것인지 선택해야 할 때 나는 보통 둘이 탐색하는 모양을 생각해본다.

DFS는 한 노드에 도달 했을 때 갈 수 있는 노드가 있는 경우 끝까지 찾고 돌아오고,

BFS는 물의 파장처럼 점진적으로 퍼지며 탐색을 진행한다.

 

따라서 이문제는 익은 토마토 중심으로 점진적으로 퍼저나가며 토마토를 익게 만들기 때문에 BFS를 선택한다.

 

문제

 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

입력

 

풀이

 

1. 시작 노드(1로 입력을 받은 지점)을 큐에 추가한다.

 

2. 큐에서 노드를 하나 뺀다.

 

3. 뺀 노드에서 상하좌우 4방향으로 유효성 검사를 한다. (이 때 유효성검사는 1. 좌표의 유효성 2. 0인지를 확인한다)

 

4. 유효한 경우 큐에 추가하고, 이동한 노드의 값 = 이전 노드의 값 + 1 해준다. (익는데 걸리는 일수를 구하기 위함)

 

5. 큐가 빌 때까지 2~4를 반복한다.

 

6. 배열의 값을 조사하여 0인 부분이 있으면 -1을 출력하고, 그렇지 않다면 최고 값 - 1을 출력한다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point{
    int row, col;
    public Point(int row, int col){this.row = row; this.col = col;}
}

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int arr[][], m, n;
    static Queue<Point> queue = new LinkedList<>();
    // 상하좌우를 나타내기 위한 배열
    static int xArr[] = {-1, 0, 1, 0}, yArr[] = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n + 1][m + 1];

        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                // bfs를 시작하는 노드를 큐에 추가
                if(arr[i][j] == 1) queue.add(new Point(i, j));
            }
        }
        System.out.println(bfs());
    }

    private static int bfs() {

        while(!queue.isEmpty()){
            Point point = queue.poll();
            int row = point.row;
            int col = point.col;

            for(int i = 0 ; i < 4; i++){
                // 상하좌우로 토마토가 익을 수 있는지 여부 확인
                if(checkLocation(row + xArr[i], col + yArr[i])){
                    // 익은 토마토를 큐에 추가
                    queue.add(new Point(row + xArr[i],col + yArr[i]));
                    // 익은 토마토의 값 = 이전에 익은 토마토의 값 + 1
                    arr[row + xArr[i]][col + yArr[i]] = arr[row][col] + 1;
                }
            }
        }
        // 최대 값을 구하기 위한 변수
        int result = Integer.MIN_VALUE;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                // 하나라도 익지 않은 토마토가 있다면 -1을 반환
                if(arr[i][j] == 0) return -1;
                // 토마토가 익는데 걸리는 시간을 구함
                result = Math.max(result, arr[i][j]);
            }
        }
        // 최대 값이 1이라면 원래부터 모두 익어있었다는 것
        if(result == 1) return 0;
        // 최대 값 - 1 --> 걸린 일수
        return (result - 1);
    }

    private static boolean checkLocation(int row, int col) {
        // 주어진 범위 밖인지 검사
        if(row < 1 || row > n || col < 1 || col > m) return false;
        // 아직 익지 않은 토마토라면 true 반환
        if(arr[row][col] == 0) return true;
        // 이미 익어있거나 빈 자리라면 false 반한
        return false;
    }
}