[백준/JAVA] 7576 토마토

---

조심!

• 시작점은 한 곳에서만 시작하지 않는다.
• 익은 토마토는 상하좌우로 사방에 영향을 준다.
• M은 세로 N은 가로이므로 상자[M][N]으로 2차원 배열을 설정해야한다.

풀이

• BFS를 사용하여 풀었다.
• 큐에 좌료값을 입력하기 위해 Pos라는 클래스를 사용하였다.
• 시작점은 한 곳만이 아니므로 시작점들을 저장할 start라는 리스트에 저장해두고, BFS 시작할 때 큐에 모두 입력하고 시작한다.
• BFS 이후에는 상자에 "0" 값이 있으면 안된다. findMax()라는 메소드를 통해 최대값(최장시간)을 구함과 동시에 "0"을 발견하게 되면 찾는것을 중지하고 바로 return한다.

---

제출 코드

import java.io.*;
import java.util.*;

class Main {

    static int[][] map;
    static int N, M;
    static Queue<Pos> q = new LinkedList<>();
    static int[] opsX = {-1, 1, 0, 0};
    static int[] opsY = {0, 0, -1, 1};
    static int count;
    static ArrayList<Pos> start = new ArrayList<>();

    static class Pos {
        int x;
        int y;

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


    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(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[M][N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == 1) {
                    count++;
                    start.add(new Pos(i, j));
                }
            }
        }
        bfs();
        bw.write(String.valueOf(findMax() - 1));

        bw.flush();
    }

    public static void bfs() {
        for (Pos pos : start) {
            q.offer(pos);
        }
        while (!q.isEmpty()) {
            Pos node = q.poll();

            for (int i = 0; i < 4; i++) {
                int newX = node.x + opsX[i];
                int newY = node.y + opsY[i];

                if (-1 < newX && newX < M && -1 < newY && newY < N) {
                    if (map[newX][newY] == 0) {
                        q.offer(new Pos(newX, newY));
                        map[newX][newY] = map[node.x][node.y] + 1;
                    }
                }
            }
        }
    }

    public static int findMax() {
        int result = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0) {
                    return 0;
                } else if (map[i][j] > result) {
                    result = map[i][j];
                }
            }
        }
        return result;
    }
}

---

백준 7576 토마토 문제 링크