[백준 7576번] 토마토

[백준 7576 URL]

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

이번 문제는 전형적이고 아주 쉬운 탐색문제입니다.

하지만, [백준 2178번 미로탐색]과는 다르게 함정(?)이 숨어있습니다.

2019/02/11 - [알고리즘 문제/백준(BOJ)] - [백준 2178번] 미로탐색

1. 데이터를 입력받는 map, 방문처리를 위한 visited 배열을 선언합니다.

2. 행과 열, 그리고 몇번을 움직였는지 count하기 위해 Node 클래스를 선언합니다.

3. 입력을 받을 때 map[row][col] == 1 인 경우는 익은 토마토이므로 tomato라는 List에 추가시켜줍니다.

그 이유는 익은 토마토들과 인접해있는 익지 않은 토마토들부터 익기시작하기 때문에 Queue에 초기에 입력받은 

토마토들을 우선적으로 추가하여 bfs를 돌려야합니다.

4. Queue에서 하나씩 꺼내면서 인접한 토마토들 중에 익지않은 토마토들을 다시 Queue에 담아주면서 진행합니다.

여기서 주의해야할 점은 map[row][col] == -1 인 경우에는 Queue에 넣어서는 안됩니다.

익은 토마토가 주변으로 퍼져나가는 경우는 익지않은 토마토가 인접한 경우이기 때문입니다.

5. bfs()가 수행되고 나면 익지않은 토마토 (map[row][col] == 0)이 있는지 확인하고 결과 값을 출력합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] dirX = { 0, 0, -1, 1 };
    public static int[] dirY = { -1, 1, 0, 0 };
    public static int[][] map;
    public static boolean[][] visited;
    public static List<Node> tomato;
    public static int N, M, ans = Integer.MIN_VALUE;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        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];
        tomato = new ArrayList<Node>();
 
        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)
                    tomato.add(new Node(i, j, 0));
            }
        }
 
        bfs();
        if(isPossible())
            System.out.println(ans);
        else
            System.out.println(-1);
    }
 
    public static void bfs() {
 
        Queue<Node> q = new LinkedList<Node>();
 
        // 초기에 입력받은 익은 토마토들을 Queue에 넣어줌
        for (Node node : tomato) {
            int row = node.row;
            int col = node.col;
            q.offer(new Node(row, col, 0));
            visited[row][col] = true;
        }
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
 
            ans = Math.max(cnt, ans);
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc] && map[nr][nc] == 0) {
                    q.offer(new Node(nr, nc, cnt + 1));
                    map[nr][nc] = 1;
                    visited[nr][nc] = true;
                }
            }
 
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
 
    public static boolean isPossible() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0)
                    return false;
            }
        }
        return true;
    }
 
}
 
class Node {
 
    int row;
    int col;
    int cnt;
 
    public Node(int row, int col, int cnt) {
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
 
}