JuSeok

7576번

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

문제 해결 순서

  1. 너비우선탐색 문제이므로 큐를 이용해 구현.
  2. tomato 배열에 현재 농장 상태를 입력받음.
  3. bfs 맨 처음에 익은 토마토들을 모두 큐에 삽입. (동시다발적으로 일어나야하므로.)
  4. 큐에서 하나씩 빼면서 익은 토마토 근접의 안 익은 토마토들을 익은 토마토로 변경.
  5. 이때 이전 토마토의 값 + 1을 대입. (며칠만에 바뀐 토마토인지 체크하기 위해서.)
  6. while문이 끝나고 tomato 배열을 체크하며 안익은 토마토가 있다면 -1 출력, 없다면 최대값 (걸린 일수) 출력.
import java.util.*;
public class Main {
    static class Pos{
        int x;
        int y;
        Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static Queue<Pos> queue = new LinkedList<>();
    static boolean visit[][];
    static int tomato[][];
    static int n;
    static int m;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        m = scan.nextInt();
        n = scan.nextInt();
        tomato = new int[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tomato[i][j] = scan.nextInt();
            }
        }

        bfs();
    }

    static void bfs(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tomato[i][j] == 1)
                    //익은 토마토가 있는 모든 위치를 큐에 담는다.
                    queue.add(new Pos(i, j));
            }
        }
        // 큐에 값이 있으면
        while(!queue.isEmpty()){
            Pos temp = queue.poll();
            visit[temp.x][temp.y] = true;

            // 위로 갈 수 있고, 방문하지 않았고, 안익은 토마토가 있다면
            if(temp.x - 1 >= 0 && !visit[temp.x - 1][temp.y] && tomato[temp.x - 1][temp.y] == 0){
                Pos ntomato = new Pos(temp.x - 1, temp.y);
                queue.add(ntomato);
                tomato[temp.x - 1][temp.y] = tomato[temp.x][temp.y] + 1;
            }
            // 아래로 갈 수 있고, 방문하지 않았고, 안익은 토마토가 있다면
            if(temp.x + 1 < n && !visit[temp.x + 1][temp.y] && tomato[temp.x + 1][temp.y] == 0){
                Pos ntomato = new Pos(temp.x + 1, temp.y);
                queue.add(ntomato);
                tomato[temp.x + 1][temp.y] = tomato[temp.x][temp.y] + 1;
            }
            // 오른쪽으로 갈 수 있고, 방문하지 않았고, 안익은 토마토가 있다면
            if(temp.y + 1 < m && !visit[temp.x][temp.y + 1] && tomato[temp.x][temp.y + 1] == 0){
                Pos ntomato = new Pos(temp.x, temp.y + 1);
                queue.add(ntomato);
                tomato[temp.x][temp.y + 1] = tomato[temp.x][temp.y] + 1;
            }
            // 왼쪽으로 갈 수 있고, 방문하지 않았고, 안익은 토마토가 있다면
            if(temp.y - 1 >= 0 && !visit[temp.x][temp.y - 1] && tomato[temp.x][temp.y - 1] == 0){
                Pos ntomato = new Pos(temp.x, temp.y - 1);
                queue.add(ntomato);
                tomato[temp.x][temp.y - 1] = tomato[temp.x][temp.y] + 1;
            }
        }

        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tomato[i][j] == 0) {
                    //토마토가 모두 익지 못한 상황이라면 -1 을 출력한다.
                    System.out.println(-1);
                    return;
                }
                max = Math.max(max, tomato[i][j]);
            }
        }
        //그렇지 않다면 최대값을 출력한다.
        System.out.println(max - 1);
    }
}

Tags