[BOJ-7576][BFS] 토마토 - Java

문제 바로가기

7576번: 토마토

몇가지 조건이 달려있는 간단한 BFS 문제입니다. 하루가 지나면 익은 토마토의 사방에 있는 토마토가 익는다고 하니, visited 배열을 활용해서 답을 구해주면 됩니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Dir{
    int y, x;
    Dir(int y, int x){
        this.y = y; this.x = x;
    }
}

public class Main {
    static int M, N;
    static int ans = 0;
    static int[][] box;
    static int[][] visited;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};
    static ArrayList<Dir> tomatoes = new ArrayList<Dir>();

    static boolean isIn(Dir cur) {
        if(0<= cur.y && cur.y < N && 0<= cur.x && cur.x < M) return true;
        else return false;
    }

    static int bfs() {
        Queue<Dir> q = new LinkedList<Dir>();
        for(Dir t : tomatoes) {
            visited[t.y][t.x] = 1;
            q.offer(t);
        }

        while(!q.isEmpty()) {
            Dir cur = q.poll();

            for(int i =0; i< 4; i++) {
                Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
                if(!isIn(next) || box[next.y][next.x] == -1 || visited[next.y][next.x] != 0 ) continue;

                q.offer(next);
                visited[next.y][next.x] = visited[cur.y][cur.x] + 1;
                ans = ans > visited[next.y][next.x] ? ans : visited[next.y][next.x]; 
            }
        }

        outer:
        for(int i = 0; i< N; i++) {
            for(int j = 0; j < M; j++) {
                if(visited[i][j] == 0 && box[i][j] != -1) {
                    ans = 0;
                    break outer;
                }
            }
        }
        return ans - 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        boolean isFull = true;
        box = new int[N][M];
        visited = new int[N][M];
        for(int i = 0; i< N; i++) {
            for(int j = 0; j < M; j++) {
                box[i][j] = sc.nextInt();
                if(box[i][j] == 1) tomatoes.add(new Dir(i, j));
                if(box[i][j] == 0) isFull = false;
            }
        }

        if(isFull) System.out.println("0");
        else System.out.println(bfs());
    }
}

익은 토마토의 자리들에게 visited = 1 을 주고 시작합니다. 참고로 visited 배열을 -1로 초기화하기 귀찮아서 맨 첨에 시작이 1이지만 답 출력할 땐 여기서 1을 빼주어야 합니다. 왜냐면 맨 첨에는 0일이니깐.

 

BFS를 돌면서 조건 체크해가면서 visited 배열 next 자리에 cur + 1을 해주면 됩니다.

 

visited 배열을 모두 업데이트해주고 나서 visited 배열에 0(못익은 토마토)이 있는지 확인을 해줍니다. 요 때 또 주의해야 할게 토마토가 들어있지 않은 칸(-1)의 visited 값은 0이기 때문에 주의해주어야 합니다.

고로 visited==0 && box != -1 까지 같이 확인해서 정답을 구해줍시다.

 

또또또 주의해야 할게 마지막 테케입니다. 이미 모든 토마토가 익은 상태가 입력으로 들어온 경우를 따로 봐줘야 합니다. 입력을 받을 때 0이 하나도 없으면 걍 0을 출력하고 끝내줍니다.

 

 

감사함니다~