[BFS] 백준 - 7576번: 토마토 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

7576번: 토마토

 

 

문제는 다음과 같다.

토마토가 익기 위해선 동서남북으로 하나의 토마토가 무조건 있어야 같이 익는다.

쉽게 말하면 익은 토마토가 동서남북으로 안 익은 토마토를 하루 단위로 익게 한다.

따라서 예제를 기준으로 보면 아래와 같이 표현할 수 있다.

 

BFS로 풀어주면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static int[][] map;
    static boolean[][] visited;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static Queue<int[]> q;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        visited = new boolean[n][m];
        q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

        try {
            bfs();
        } catch (Exception e) {
            System.out.println(-1);
            return;
        }

        int k = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
                k = Math.max(k, map[i][j]);
            }
        }

        System.out.println(k - 1);
    }

    private static void bfs() {
        int[] point = q.poll();
        int x = point[0];
        int y = point[1];
        visited[x][y] = true;
        q.add(new int[]{x, y});

        while (!q.isEmpty()) {
            int[] list = q.poll();
            int xx = list[0];
            int yy = list[1];

            for (int i = 0; i < 4; i++) {
                int nowX = xx + dx[i];
                int nowY = yy + dy[i];

                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                    if (!visited[nowX][nowY] && map[nowX][nowY] == 0) {
                        map[nowX][nowY] = map[xx][yy] + 1;
                        visited[nowX][nowY] = true;
                        q.add(new int[]{nowX, nowY, map[xx][yy] + 1});
                    }
                }
            }
        }

        visited = new boolean[n][m];
    }
}

 

처음에 풀었을 때 큐가 bfs 함수 안에 있어서 1, 1부터 시작하여 안 익은 토마토 다 익히고 다른 익은 토마토 지점에서 또 BFS를 돌려서 날짜가 자신보다 클 때까지 돌리다 보니 시간 초과가 났었다.

 

그래서 큐를 스태틱으로 빼서 각 지점에서 bfs를 돌리면 답이 간단히 나오는 문제였다..

아 그리고 0, 0을 쳤을 때 nullPointer가 떠서 try~catch로 오류 발생 시 -1을 출력하였다.