[백준] 7576번 토마토 - Java, 자바

난이도

골드5

문제

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

풀이

최소일수를 구하라고 했으니 BFS로 접근해야한다.
문제의 로직은 일반적인 BFS 문제와 유사하다.

하지만 이해가 안가는 부분이 있었다.
처음에 주어진 익은 토마토의 개수가 여러 개 일 수 있다.
2개가 있을 때 하루가 지나면 2개의 토마토 주위가 동시에 익는다.
이것을 BFS에서 어떻게 표현해야 할지 고민했다.

생각해보니 BFS는 너비 탐색이기 때문에, 뎁스가 1인 요소 모두 처리, 뎁스가 2인 요소 모두 처리 ... 이런 식으로 진행되기 때문에
아래의 식으로 다음 뎁스가 넘어갈 때 현재 뎁스에서 1 값을 증가시켜주는 식이 성립된다.

    if (map[nx][ny] == 0) {
    	map[nx][ny] = map[x][y] + 1;
        q.add(new int[]{nx, ny});
    }

예제 입력 3을 기준으로 더 설명해보자면,
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

초기에 (0,0), (3,5) 가 큐에 들어간다.
(0,0)이 poll()된 후, map[1][0]=map[0][0]+1=2가 되고, (1,0)이 큐에 들어가고
(3,5)가 poll()된 후, map[2][5]=map[3][5]+1=2가 되고, (2,5)이 큐에 들어간다.

현재 큐 상태 (1,0), (2,5)
(1,0)이 poll()된 후, map[2][0]=map[1][0]+1=3가 되고, (2,0)이 큐에 들어가고
(2,5)가 poll()된 후, map[1][5]=map[2][5]+1=3가 되고, (1,5)이 큐에 들어간다.

이런 식으로 반복된다.

위처럼 이해하고 코드를 짜면 수월할 것이다!

코드

package 그래프탐색;


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


public class BOJ7576 {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    static int[][] map;
    static Queue<int[]> q = new LinkedList<>();

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

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        map = new int[n][m];


        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());
                if (map[i][j] == 1) {
                    q.add(new int[]{i, j});
                }
            }
        }

        System.out.println(bfs());
    }

    private static int bfs() {
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int x = t[0];
            int y = t[1];
            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 (map[nx][ny] == 0) {
                    map[nx][ny] = map[x][y] + 1;
                    q.add(new int[]{nx, ny});
                }
            }
        }

        int max = Integer.MIN_VALUE;
        if (checkZero()) {
            return -1;
        } else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (max < map[i][j]) {
                        max = map[i][j];
                    }
                }
            }

            return max - 1;
        }


    }

    private static boolean checkZero() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0)
                    return true;
            }
        }
        return false;
    }
}