[백준] 7576번 토마토(java)

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

7576번: 토마토

bfs 문제이다.

 

핵심

이 문제는 시작점이 여러 개인 bfs 문제이다.

시작점이 여러 개라고 해서 크게 달라지는 것은 없다.

각 시작점에서 점차 값을 증가시키면 쉽게 풀 수 있다.

 

 

정답 코드

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

public class Main {
    static int N;
    static int M;
    static int[][] map;
    static int[][] result;
    static boolean[][] visited;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        result = new int[M][N];
        visited = new boolean[M][N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == -1) result[i][j] = -1;
            }
        }

        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    result[i][j] = 1;
                }
            }
        }

        while (!q.isEmpty()) {
            int[] move = q.poll();

            for (int i = 0; i < 4; i++) {
                int moveY = move[0] + dy[i];
                int moveX = move[1] + dx[i];
                if (0 <= moveY && moveY < M && 0 <= moveX && moveX < N) {
                    if (map[moveY][moveX] == 0 && result[moveY][moveX] == 0) {
                        result[moveY][moveX] = result[move[0]][move[1]] + 1;
                        q.offer(new int[]{moveY, moveX});
                    }
                }
            }
        }
        int max = 0;
        boolean pass = false;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (result[i][j] == 0){
                    pass = true;
                    break;
                }
                max = Math.max(max, result[i][j]);
            }
        }

        if (pass)
            System.out.println(-1);
        else {
            System.out.println(max-1);
        }

    }
}

해설

우선 입력을 받을 때 -1 이면 -> 토마토가 없는 장소이므로 result에도 -1을 넣어준다.

이유는 맨 마지막에 0으로 판단하는 로직이 있기 때문이다.

각 시작점을 큐에 넣어준다. 

시작점으로부터 네 방향으로 이동하며, 값을 1씩 증가시킨다. 단 토마토가 아직 안 익었고, 방문한 적이 없어야 한다.

result에 담긴 값을 확인하여 0 있다면 -1을 출력하고, 없다면 그중 최댓값에서 -1을 한 값을 출력한다.

-1을 하는 이유는 첫 시작을 1로 시작했기 때문이다.

 

 

배운 점

처음에 시작점이 여러 개이기 때문에 살짝 당황했었다.

하지만 처음부터 bfs에 넣고 풀면 쉽게 풀린다는 것을 파악하고 풀었다.

 bfs는 대부분 비슷한 패턴이 있다고 생각된다.