[BFS] 백준-7576 토마토 골드5

백준-7576 : 토마토

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

7576번: 토마토

 

풀의

• 익어있는 토마토들을 넣어주고 BFS를 진행
  
  • BFS를 진행할때 익어있는 경우 현재 값에 1을 더해서 경과를 표시 더 작은값일 경우 값 갱신
  • 초기 익어있는 토마토값이 1이므로 총 경과일은 가장 큰 값에서 1을 뺀 값을 리턴

코드 (java)

import java.util.*;

class Baejoon7576Node {

    private int x;
    private int y;


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

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }

}

public class Baejoon7576 {

    public static int n, m;
    public static int[][] tomatoInfoGraph;

    // 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};


    public static void bfs() {
        Queue<Baejoon7576Node> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tomatoInfoGraph[i][j] == 1) {
                    q.offer(new Baejoon7576Node(i, j));
                }
            }
        }


        while (!q.isEmpty()) {

            Baejoon7576Node node = q.poll();
            int x = node.getX();
            int y = node.getY();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 공간을 벗어난 경우 무시
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                // 토마토가 없을 경우 무시
                if (tomatoInfoGraph[nx][ny] == -1) continue;
                // 익지 않았거나, 더 짧은 경과일이경우 실행
                if (tomatoInfoGraph[nx][ny] == 0 || tomatoInfoGraph[nx][ny] > tomatoInfoGraph[x][y] + 1) {
                    tomatoInfoGraph[nx][ny] = tomatoInfoGraph[x][y] + 1;
                    q.offer(new Baejoon7576Node(nx, ny));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();

        sc.nextLine();

        tomatoInfoGraph = new int[n][];


        // 입력 받기
        for (int i = 0; i < n; i++) {
            String[] tempTomatoInfos = sc.nextLine().split(" ");
            tomatoInfoGraph[i] = Arrays.stream(tempTomatoInfos).mapToInt(Integer::parseInt).toArray();
        }

        bfs();

        boolean falseFlag = false;
        int maxDay = -1;
        // 정렬 후 그래프 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tomatoInfoGraph[i][j] == 0) {
                    falseFlag = true;
                    break;
                }
                if (maxDay < tomatoInfoGraph[i][j]) {
                    maxDay = tomatoInfoGraph[i][j];
                }
            }
            // 안익은게 존재 할때
            if (falseFlag) {
                break;
            }
        }

        if (falseFlag) {
            System.out.println("-1");
        } else {
            System.out.println(maxDay - 1);
        }

    }
}