[백준] 7576번. 토마토 (JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    static int[][] arr;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        visited = new boolean[n][m];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        if (check() == 0) {
            System.out.println(0);
        } else {
            Bfs();

            if(check() == 0){
                int max = 0;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if(arr[i][j] > max){
                            max = arr[i][j];
                        }
                    }
                }
                System.out.println(max -1);
            }else{
                System.out.println(-1);
            }
        }

    }

    public static void Bfs(){
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(arr[i][j] == 1){
                    queue.offer(new int[] {i, j});
                }
            }
        }
        while(!queue.isEmpty()){
            int now[] = queue.poll();
            visited[now[0]][now[1]] = true;
            for(int k = 0; k < 4; k++){
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x >= 0 && y >= 0 && x < n && y < m){
                    if(arr[x][y] == 0 && !visited[x][y]){
                        visited[x][y] = true;
                        arr[x][y] = arr[now[0]][now[1]] + 1;
                        queue.offer(new int[] {x , y});
                    }
                }
            }
        }
    }
    
    public static int check() {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] != 0) {
                    count++;
                }
            }
        }
        if (count == n * m) {
            return 0;
        } else {
            return -1;
        }
    }
}

메서드에 대한 설명을 먼저 하고 메인코드에 대해 알아보자.

 

Bfs메서드는 bfs를 실행한다. 여기서 좌표를 따로 받지 않고 메서드에 들어온 뒤에 모든 인덱스를 탐색하며 큐에 추가하는 이유는 익을 수 있는 과일의 위치로부터 범위적 탐색이 이루어져야 하기 때문이다. 즉, (0,0)과 (5,3)에 익은 과일이 있다면 (0,0)부터 쭉 탐색하고 다시 (5,3)을 탐색하고 하는 것이 아닌 동시에 이루어져야 한다는 것이다. (그렇기에 배열에 넣은 순서대로 나오는 큐를 사용하는 것이 여기서 역시 이용된다.)

 

check메서드는 현재 모든 과일이 익거나 빈 과일 바구니인지, 아니면 익지 않은 과일이 있는지 체크하는 메서드이다.

 

메인 코드에서는 먼저 check()를 통해 체크한 뒤에 진행하게 되고, 아직 익지않은 과일이 있다면 Bfs를 통해 전체 과일에 대한 동작을 실행한다.

이때 날짜를 자동으로 늘려주는 bfs를 사용해 출력하게 된다.

arr[x][y] = arr[now[0]][now[1]] + 1;

bfs메서드의 이 부분을 이용하는 것인데, 현재 좌표보다 +1을 해줌으로써 최댓값을 계속 갱신해 나가며 bfs를 진행하는 것이다.