[백준 7576 java 자바] 토마토 (BFS/DFS)

[Gold V] 토마토 - 7576

문제 링크

성능 요약

메모리: 142664 KB, 시간: 824 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

---

풀이

BFS를 통해 지도에서 최단거리 찾듯이 이전 값 + 1 로 지도를 계속 갱신해준다. 그렇게 지도에서 접근 가능한(상하좌우) 모든 0이 사라지면
지도에서 가장 큰 값 -1이 최종 걸린 날짜, 지도에 0이 존재하면 익기 불가능한 토마토가 존재하는 것이다.

---

코드

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

public class Main {
//변수 선언
    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static String[] strs; 
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};


    static int h, w; //세로 가로
    static int[][] graph;//토마토 지도
    static Queue<Node> link = new LinkedList<>(); //BFS를 위한 토마토 Queue



    public static void main(String[] args) throws IOException {

        //입력
        --------------------------------------------------------------------------------
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        strs = br.readLine().split(" ");
        w = Integer.parseInt(strs[0]);
        h = Integer.parseInt(strs[1]);

        graph = new int[h][w];

        for (int i = 0; i < h; i++) {
            strs = br.readLine().split(" ");
            for (int j = 0; j < w; j++) {
                graph[i][j] = Integer.parseInt(strs[j]);
                if (graph[i][j] == 1) link.offer(new Node(i, j)); //초기에 토마토가 있는 1의 위치를 모두 담는다.
            }
        }
        --------------------------------------------------------------------------------


        //수행
        --------------------------------------------------------------------------------
        while (!link.isEmpty()) { //익힐 토마토(0인 좌표)가 없을 때까지 반복
            Node poll = link.poll();
            for (int i = 0; i < 4; i++) {
                int nX = dx[i] + poll.x;
                int nY = dy[i] + poll.y;
                if(nX < 0 || nX >= h || nY < 0 || nY >= w) continue;
                if (graph[nX][nY] == 0) { //익은 토마토 상하좌우에 있는 익을 토마토라면
                    graph[nX][nY] = graph[poll.x][poll.y] +1; //이전 값 + 1 (최종 날짜를 재기 위함)
                    link.add(new Node(nX, nY));
                }
            }
        }
        --------------------------------------------------------------------------------

        int max = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (graph[i][j] == 0) {
                    System.out.println("-1"); //안익은 토마토가 있으면 -1 출력
                    return;
                }
                max = Math.max(max, graph[i][j]); //최대값 == 최종 날짜
            }
        }
        System.out.println(max -1);
    }
}