[백준] 토마토 (7576) Java

문제 링크

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

7576번: 토마토

 

문제 요약

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

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

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

 

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

 

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다.

둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다.

정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

출력

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

접근법

익은 토마토를 탐색하며 인접한 안 익은 토마토를 익게 하면 되는, 간단한 BFS 문제이다.

 

N과 M의 최댓값이 1,000이므로 BFS를 활용한 완전탐색으로 제한 시간 내에 충분히 풀 수 있다.

어차피 익은 토마토는 인접한 안익은 토마토를 모두 익히기 때문에, 한 번 탐색한 익은 토마토들은 다시 확인할 필요가 없다. 다음 날에는 인접한 토마토들이 모두 익어있기 때문이다.

따라서 새롭게 익은 토마토들만 계속 bfs로 탐색해나가면서, 토마토가 전부 익었을 때 bfs를 멈추고 전부 익히는데 며칠이 걸렸는지 출력하면 된다.

 

기본적인 알고리즘은 BFS와 동일하고, 몇 가지 조건만 추가해주면 된다.

1. 입력 받으면서 안 익은 토마토의 개수를 미리 센다. BFS를 하며 토마토가 하나 익을 때마다 카운트 해서, 남아있는 안 익은 토마토가 없으면 BFS를 종료하고 정답을 출력한다.
2. "하루가 지났다"는 걔념을 BFS로 표현하기 위해, 해당 일자에 체크해야 할 익은 토마토의 개수에 대한 카운터 변수를 사용한다. 익은 토마토 하나를 queue에서 꺼낼 때마다 해당 변수에서 1을 빼준다. 이 변수가 0이 되면 하루가 지났다는 의미이므로 반환할 정답에 1을 더해준다.
3. BFS를 하기 전에 창고에 안 익은 토마토가 없으면 0 출력. BFS가 끝났는데도 안 익은 토마토가 존재하면 -1을 출력한다.

2번 조건은 코드로 보는 것이 더 이해가 잘 될 것이다.

 

 

시간 복잡도

이전 날에 탐색했던 익은 토마토는 다시 탐색하지 않으므로 O(N * M)

 

 

공간 복잡도

N * M 개의 int를 저장할 배열, 최대 (N * M - 1) * 2 개의 int가 들어갈 수 있는 queue

따라서 약 3(N * M) * 4 bytes 정도가 필요하다.

 

 

풀면서 놓쳤던 점

딱히 없다.

 

 

이 문제에서 얻어갈 점

이전에 비슷한 유형의 BFS 문제를 푼 적이 있다.

"하루가 지났다"는 개념을 카운터 변수와 if문으로 구현해야 하는데, 이런 비슷한 조건을 요구하는 BFS 문제가 좀 있는 것 같다.

이 부분을 집고 넘어갈 수 있었다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main
{
    static int rows, cols; //토마토 창고의 행,열 길이
    static int[][] warehouse; //토마토 창고의 토마토를 int[][] 배열로 표현

    public static void main(String[] args) throws IOException
    {
        //토마토 창고 크기와 토마토 상태 및 위치를 입력 받음
        readInput();

        //unripeCnt => 안 익은 토마토의 개수
        //tomatoesOfDayCnt => 0이 되면 하루가 지났다는 의미
        //어떤 날에 익은 토마토가 k개 있을 때, k개의 토마토를 하나씩 확인하며
        //인접한 토마토를 전부 익히면 하루가 지났다는 것이다.
        //이 k값을 저장해두고 하루가 지났다는 것을 확인하기 위해 쓰는 변수가 tomatoesOfDayCnt
        int unripeCnt, tomatoesOfDayCnt;
        unripeCnt = 0;
        tomatoesOfDayCnt = 0;

        //BFS에 사용할 queue
        Queue<RipeTomato> ripeTomatoQueue = new LinkedList<>();

        //warehouse[][]를 탐색하며 토마토의 상태를 확인
        for (int row = 0; row < rows; row++)
        {
            for (int col = 0; col < cols; col++)
            {
                //안 익은 토마토의 개수를 센다
                if (warehouse[row][col] == 0)
                    unripeCnt++;
                //익은 토마토면 bfs를 위해 queue에 넣어준다
                else if (warehouse[row][col] == 1)
                    ripeTomatoQueue.add(new RipeTomato(row, col));
            }
        }

        //위에서 queue에 넣어준 tomatoesOfDayCnt 개의 토마토들이
        //인접한 안 익은 토마토를 전부 익히면 둘째날이 된다.
        tomatoesOfDayCnt = ripeTomatoQueue.size();

        //정답 출력
        System.out.println(getRipeTime(ripeTomatoQueue, unripeCnt, tomatoesOfDayCnt));
    }

    static int getRipeTime(Queue<RipeTomato> ripeTomatoQueue, int unripeCnt, int tomatoesOfDayCnt)
    {
        //안 익은 토마토가 존재하지 않으면 0 반환
        if (unripeCnt == 0)
            return 0;

        int ripeTime = 1; //반환할 변수. 모든 토마토를 익히는데 걸리는 날짜.
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //bfs를 위한 방향 배열
        RipeTomato ripeTomato;
        int unripeRow, unripeCol;

        //BFS
        while (!ripeTomatoQueue.isEmpty())
        {
            ripeTomato = ripeTomatoQueue.poll();
            tomatoesOfDayCnt--; //이 값이 0이 되면 하루가 지난 것.

            //인접한 토마토를 확인
            for (int[] dir : dirs)
            {
                //인접한 지역이 범위를 벗어나거나, 안익은 토마토가 아니면 continue
                if (!unripeTomatoExists(ripeTomato.row + dir[0], ripeTomato.col + dir[1]))
                    continue;

                //최적화를 위해 토마토가 전부 익으면 바로 return
                unripeCnt--;
                if (unripeCnt == 0)
                    return ripeTime;

                unripeRow = ripeTomato.row + dir[0];
                unripeCol = ripeTomato.col + dir[1];

                //안익은 토마토를 익은 토마토로 바꿔주고 queue에 넣어준다
                warehouse[unripeRow][unripeCol] = 1;
                ripeTomatoQueue.add(new RipeTomato(unripeRow, unripeCol));
            }

            //하루가 지난 경우 ripeTime++
            //새롭게 익은 토마토 개수 == ripeTomatoQueue.size()
            if (tomatoesOfDayCnt == 0)
            {
                tomatoesOfDayCnt = ripeTomatoQueue.size();
                ripeTime++;
            }
        }

        //bfs가 끝났는데 안 익은 토마토가 남아있는 경우.
        return  -1;
    }

    static boolean unripeTomatoExists(int row, int col)
    {
        return row >= 0 && row < rows && col >= 0 && col < cols && warehouse[row][col] == 0;
    }

    static void readInput() throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        cols = Integer.parseInt(st.nextToken());
        rows = Integer.parseInt(st.nextToken());

        warehouse = new int[rows][cols];

        for (int row = 0; row < rows; row++)
        {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < cols; col++)
                warehouse[row][col] = Integer.parseInt(st.nextToken());
        }

        br.close();
    }
}

class RipeTomato
{
    int row;
    int col;

    RipeTomato(int row, int col)
    {
        this.row = row;
        this.col = col;
    }
}