[알고리즘] 백준 7576 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

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

public class BOJ_7576 {
    static int m;
    static int n;
    static int[][] map;
    static boolean[][] visited;
    static int count = 0;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        map = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1];

        // init
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(map[i], 0);
        }

        for (int i = 1; i < n + 1; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");

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

        List<Location> list = new ArrayList<Location>();

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

    public static void bfs(List<Location> loc) {
        Queue<Location> qu = new LinkedList<Location>();
        int day = 0;

        for (int i = 0; i < loc.size(); i++) {
            Location currentLoc = loc.get(i);
            qu.add(currentLoc);
        }

        while (!qu.isEmpty()) {
            Location temp = qu.poll();
            day = temp.value;

            for (int i = 0; i < 4; i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];

                if (nx > 0 && nx < n + 1 && ny > 0 && ny < m + 1) {
                    if (map[nx][ny] == 0) {
                        qu.add(new Location(nx, ny, temp.value + 1));
                        map[nx][ny] = map[temp.x][temp.y] + 1;
                    }
                }
            }
        }
        if (checkTomato())
            System.out.println(day);
        else
            System.out.println(-1);
    }

    public static boolean checkTomato() {

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

    static class Location {
        int x;
        int y;
        int value;

        public Location(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }
}

익은 토마토의 상,하,좌,우 인덱스값이 하루마다 익어간다. 

 

nx, ny(상하좌우 인덱스)값을 검증하면서 bfs를 돌리면 된다.

 

map[nx][ny]의 값과 Location.value의 값은 map[temp.x][temp.y] + 1로 만들어 준다.

 

이를 통해 토마토가 익었을 당시의 날짜를 찾을 수 있다.

 

또한 마지막으로 익은 토마토 Location의 value값 == map[][]의 최대값 == 토마토가 모두 익은 날짜이다.

 

또한 신경써줘야 할 것이 있는데, 토마토가 모두 익지 못하게 되는 경우에는 -1을 출력해야한다. 

 

BFS가 완료된 후 map[][]에 0이 한개라도 있으면 토마토가 모두 익지 않은 것이기 때문에 이러한 경우에 -1을 출력하도록 하여 문제를 해결하였다.