BOJ - 토마토 (7576)

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

7576번: 토마토

 

• 그래프 탐색 BFS 문제이다.
  • 초기 맵 초기화 시, 바꿔야 할 토마토 수를 세어 노드 방문시 개수를 차감하였다.
    • 탐색이 끝난 후 토마토 수를 다 못했다면 -1
    • 탐색이 끝났다면 최단 경로(BFS 깊이)를 출력했다.

 

 

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


public class Main {

    public static int N;
    public static int M;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int[][] tomatoMap = new int[M + 1][N + 1];
        boolean[][] visit = new boolean[M + 1][N + 1];

        Queue<State> queue = new LinkedList<>();

        int numOftomato = 1;
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                tomatoMap[i][j] = Integer.parseInt(st.nextToken());

                if (tomatoMap[i][j] == 1) {
                    queue.offer(new State(i, j, 1));
                }

                if (tomatoMap[i][j] == 0) {
                    numOftomato += 1;
                }
            }
        }

        int maxDepth = -1;
        while (!queue.isEmpty()) {
            State node = queue.poll();
            if (node.row > M || node.row <= 0) continue;
            if (node.col > N || node.col <= 0) continue;
            if (visit[node.row][node.col] == true) continue;
            if (tomatoMap[node.row][node.col] == -1) continue;

            visit[node.row][node.col] = true;
            if (tomatoMap[node.row][node.col] == 0) {
                numOftomato -= 1;
            }

            maxDepth = Math.max(node.depth, maxDepth);

            queue.offer(new State(node.row + 1, node.col, node.depth + 1));
            queue.offer(new State(node.row - 1, node.col, node.depth + 1));
            queue.offer(new State(node.row, node.col + 1, node.depth + 1));
            queue.offer(new State(node.row, node.col - 1, node.depth + 1));
        }

        if (numOftomato > 1) {
            System.out.println(-1);
        } else {
            System.out.println(maxDepth - 1);
        }
    }
}

class State {
    public int row;
    public int col;
    public int depth;

    public State(int row, int col, int depth) {
        this.row = row;
        this.col = col;
        this.depth = depth;
    }
}