[백준문제풀이] 7576 토마토 java 문제풀이

나는야~ 케챱될거야하~!

접근법 : 

**1) 어떻게 풀 것인가?**

bfs문제다. 

다른 bfs문제를 풀다가 약간 헷갈려서... 내가 bfs를 완전히 습득하지 못한것같다는 생각에

원래 풀려던 문제보다 아래 단계인 골드5를 선택했다..

기본 bfs문제와 다른것은, 시작점이 여러개라는것이다. ( 토마토의 존재 공간이 여러개)

**2) 시간복잡도**

1초다. 딱히 시간 때문에 틀릴 문제는 아닌것같다.

**3) 공간복잡도**

256mb로 공간은 넉넉한편인것같다

**4) 풀면서 놓쳤던점**

시작점이 여러개일때 어떻게 풀어야 되는지!

**5) 이 문제를 통해 얻어갈 것**

시작점이 여러개인 bfs문제를 어떻게 처리할것이냐? 에 대한 생각!

(bfs응용)

 

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

public class Main {

    static class location {
        public int tn;
        public int tm;

        location(int tn, int tm) {
            this.tn = tn;
            this.tm = tm;
        }
    }

    static int[] nd = {-1, 0, 1, 0};
    static int[] md = {0, -1, 0, 1};
    static Queue<location> queue;
    static int[][] maps;
    static boolean[][] visit;
    static int zt, mt, day = 0;
    static int n, m;
    static int v;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        queue = new LinkedList<>();
        m = Integer.parseInt(strings[0]);
        n = Integer.parseInt(strings[1]);
        v = -1;
        maps = new int[n][m];
        visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            String[] inputT = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                maps[i][j] = Integer.parseInt(inputT[j]);
                if (Integer.parseInt(inputT[j]) == 1) {
                    queue.add(new location(i, j));
                } else if (Integer.parseInt(inputT[j]) == 0) {
                    zt++;
                } else {
                    mt++;
                }
            }
        }
        if ((n * m) == (queue.size() + mt)) {
            System.out.println(0);
        } else if (queue.isEmpty()) {
            System.out.println(-1);
        } else {
            location lc = queue.peek();
            visit[lc.tn][lc.tm] = true;
            bfs();
            System.out.println(findday());
        }
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            location lc = queue.poll();
            for (int i = 0; i < 4; i++) {
                int a = lc.tn + nd[i];
                int b = lc.tm + md[i];
                if (a >= 0 && a < n && b >= 0 && b < m) {
                    if (!visit[a][b]) {
                        visit[a][b] = true;
                        if (maps[a][b] == 0) {
                            queue.add(new location(a, b));
                            maps[a][b] = maps[lc.tn][lc.tm] + 1;
                        }
                    }
                } else continue;
            }
        }
    }

    static int findday() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(maps[i][j] == 0){
                    return -1;
                }
                else{
                    v = Math.max(v,maps[i][j]);
                }
            }
        }
        return v-1;
    }
}