[BOJ] 7576 - 토마토

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/7576

7576번: 토마토

난이도: 실버 1

사용 언어: JAVA

 

토마토를 담는 큰 상자가 있고, 이 상자는 M x N의 크기를 가집니다. 이 상자에 토마토를 보관하게 되는데, 토마토 중에는 익은 토마토도 있고, 안 익은 토마토도 있습니다. 익은 토마토는 1, 안 익은 토마토는 0, 그리고 아무것도 들어있지 않은 칸은 -1로 표시됩니다. 안 익은 토마토는 인접한 곳에 익은 토마토가 존재하면 그 영향을 받아 하루가 지나 익게 됩니다. 

 

안 익은 토마토가 혼자 저절로 익는 상황은 없다고 가정하고, 토마토의 상하좌우에 다른 토마토가 존재하면, 이를 인접했다고 표현합니다. 이때, 며칠이 지나면 상자 안의 모든 토마토가 익는지, 그 최소 일수를 구하는 문제입니다. 그리고 혹시나 빈칸으로 인해 모든 토마토를 익게 만들 수 없으면, -1을 출력합니다.

 

풀이

이 문제는 BFS를 이용해 해결할 수 있고, 큐를 이용해 BFS를 구현했습니다. 우선 입력 값들을 이용해 M x N 크기의 상자를 2차원 배열로 표현합니다. 그리고 익은 토마토들의 위치를 큐에 넣어줍니다. 그리고 한 번의 반복문을 도는 동안 (하루가 지나는 동안), 큐에 있는 모든 위치를 빼내어 BFS를 수행하여 인접한 토마토들을 익게 만들고, 새롭게 익은 토마토들을 큐에 다시 넣어줍니다.

 

이러한 작업을 큐에 더 이상 넣을 토마토가 없을 때까지 반복합니다. 그리고 이때, 빈칸과 원래 익어있던 토마토, 그리고 반복문을 돌며 새롭게 익게 된 토마토들의 합이 M x N의 값과 같지 않으면 -1을 출력하고, 그렇지 않으면 반복문을 몇 번 돌았는지(며칠이 지났는지)를 출력해 줍니다.

 

그림을 통해 단계를 밟아가보겠습니다.

 

가장 좌측 상단의 초기 상태로 부터 마지막 그림까지 총 6일이 소요되는 것을 확인할 수 있습니다.

 

큐에 상자 내에서의 토마토 위치를 넣기 위해 position이라는 class를 선언하여 사용하였고, BFS 함수 내에서 배열의 크기를 벗어나지 않도록, 조건문을 걸어주었습니다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class position { // 토마토의 위치 정보를 큐에 넣기 위한 class 생성
    int x;
    int y;
}
 
class Main {
 
    static int cnt=0;
    static Queue<position> q = new LinkedList<position>(); // 큐를 이용해 BFS 구현
    static int N,M;
 
    public static void bfs(position p, int arr[][]){
        if(p.y-1 >=0) {
            position p1 = new position();
            if (arr[p.x][p.y - 1] == 0) {
                arr[p.x][p.y - 1] = 1;
                cnt++; // 매일 밤 새롭게 익는 토마토 수 카운팅
                p1.x = p.x;
                p1.y = p.y - 1;
                q.add(p1); // 새롭게 익은 토마토를 큐에 삽입
            }
        }
        if(p.x+1 < M) {
            position p2 = new position();
            if (arr[p.x+1][p.y] == 0) {
                arr[p.x+1][p.y] = 1;
                cnt++;
                p2.x = p.x +1;
                p2.y = p.y;
                q.add(p2);
            }
        }
        if(p.y+1 < N) {
            position p3 = new position();
            if (arr[p.x][p.y + 1] == 0) {
                arr[p.x][p.y + 1] = 1;
                cnt++;
                p3.x = p.x;
                p3.y = p.y + 1;
                q.add(p3);
            }
        }
        if(p.x-1 >=0) {
            position p4 = new position();
            if (arr[p.x-1][p.y] == 0) {
                arr[p.x-1][p.y] = 1;
                cnt++;
                p4.x = p.x-1;
                p4.y = p.y;
                q.add(p4);
            }
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
        M = sc.nextInt();
        int [][] arr = new int[M][N];
        int i,j;
        for(i=0;i<M;i++) {
            for (j = 0; j < N; j++) {
                arr[i][j] = sc.nextInt();
                if (arr[i][j] == 1) {
                    position p = new position();
                    p.x = i;
                    p.y = j;
                    q.add(p); // 처음부터 익어있던 토마토들의 위치를 큐에 삽입
                    cnt++; // 원래 익어있던 토마토의 개수 카운팅
                }
                else if(arr[i][j] == -1)
                    cnt++; // 비어있는 칸의 개수 카운팅
            }
        }
 
        int times = 0;
        while(true) {
            int k = q.size();
            if(cnt==N*M) { // 종료조건: 상자의 크기와 cnt의 크기가 같을 때. cnt는 빈칸 + 원래 익은 토마토 + 중간에 익은 토마토
                System.out.println(times);
                break;
            }
            if(k==0) { // 상자의 크기와 cnt가 같기 전에 더 이상 익게 만들 토마토가 없으면 -1
                System.out.println("-1");
                break;
            }
            for (i = 0; i < k; i++) { // 하루가 지날 때 마다 큐를 비워줌
                position p = new position();
                p = q.remove();
                bfs(p, arr);
            }
            times++;
        }
    }
}