🥇[백준, 7576] 토마토 (Java)

 

문제 링크

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

7576번: 토마토

 

난이도

 

시간제한

1초

 

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다.

토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.
보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.
대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.

철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

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

 

입력

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

둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다.
즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다.
하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다.
정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

출력

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

 

입출력 예시 1

입력

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

 

출력

6

 

입출력 예시 2 ( 토마토가 모두 익지 못하는 상태 )

입력

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

 

출력

-1

 

입출력 예시 3 ( 저장될 때부터 토마토가 모두 익어있는 상태 )

입력

2 2
1 -1
-1 1

 

출력

0

---

문제 풀이 과정

예시를 통해 문제 이해하기

 

예시 1을 살펴보자.

 

Day 0 (처음 상태)

1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

 

Day 1

1 -1 0 0 0 0
1 -1 0 0 0 0
0 0 0 0 -1 1
0 0 0 0 -1 1

 

Day 2

1 -1 0 0 0 0
1 -1 0 0 0 1
1 0 0 0 -1 1
0 0 0 0 -1 1

 

Day 3 

1 -1 0 0 0 1
1 -1 0 0 1 1
1 1 0 0 -1 1
1 0 0 0 -1 1

 

Day 4

1 -1 0 0 1 1
1 -1 0 1 1 1
1 1 1 0 -1 1
1 1 0 0 -1 1

 

Day 5

1 -1 0 1 1 1
1 -1 1 1 1 1
1 1 1 1 -1 1
1 1 1 0 -1 1

 

Day 6

1 -1 1 1 1 1
1 -1 1 1 1 1
1 1 1 1 -1 1
1 1 1 1 -1 1

이러한 과정을 거쳐서 토마토가 모두 익는 데에는 6일이 걸린다.

 

하루가 지날 때마다 토마토의 상하좌우로 한 칸씩의 토마토가 모두 익게 된다.

이를 통해 이 문제에서는 BFS의 개념이 쓰이는 것을 알 수 있다.

 

해당 개념에 대해 자세히 알고 싶다면 참고하길 바란다.

[알고리즘] BFS

 

입력 값 저장하기

 

총 4가지 요소를 선언해야 한다.

 

1. 상자에 담긴 토마토를 저장할 배열 (board)

2. BFS 구현을 위해 쓰일 큐 (queue)

3. 상자의 가로 칸의 수 (M)

4. 상자의 세로 칸의 수 (N)

 

public class BOJ_7576 {
    static int[][] board;
    static Queue<Tomato> queue;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        queue = new LinkedList<>();

        M = Integer.parseInt(st.nextToken());  // 가로
        N = Integer.parseInt(st.nextToken());  // 세로
        board = new int[N][M];

        // 토마토 칸 입력 받기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 1) {
                    queue.offer(new Tomato(i, j));
                }
            }
        }
    }
}

토마토 칸을 입력받으면서 해당 칸의 토마토가 익어있는 경우 큐에 추가한다.

 

토마토 클래스 구현

 

토마토의 위치를 저장하기 위해서는 해당 토마토의 x좌표, y좌표를 저장해야 한다.

그를 위해 x좌표와 y좌표를 가지는 토마토 클래스를 구현한다.

class Tomato {
    int x;
    int y;

    Tomato(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

bfs 메서드 구현

 

public static int bfs() {
    // 상하좌우
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    int day = 0;
    int size = queue.size();

    while (!queue.isEmpty()) {
        for (int i = 0; i < size; i++) {
            Tomato tomato = queue.poll();

            int x = tomato.x;
            int y = tomato.y;

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

                if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) {
                    continue;
                }

                if (board[nx][ny] == 0) {
                    board[nx][ny] = 1;
                    queue.offer(new Tomato(nx, ny));
                }
            }
        }
        size = queue.size();
        day += 1;
    }

    if (checkTomato()) return day - 1;
    return -1;
}

 

하루 동안 토마토를 탐색하는 과정을 살펴보자.

 

1. 큐의 맨 앞에 존재하는 토마토를 제거한다.

2. 해당 토마토의 상하좌우를 확인하며 범위 내의 좌표인지 확인한다.

3. 2의 조건을 만족하고 칸의 값이 0인 경우 칸의 값을 1로 바꾼 후 큐에 넣는다. 즉 토마토를 익힌다.

4. 큐에 들어가 있는 토마토 개수 즉 큐의 사이즈만큼 1, 2, 3 과정을 반복한다.

5. 큐의 사이즈를 새로 저장한다.

6. 날짜를 하루 더한다.

 

위에서 설명했던 예시와 함께 좀 더 자세히 살펴보자.

모든 과정은 큐가 비게 되면 종료된다.

 

처음 토마토 칸을 입력받으면서 익어있는 토마토의 경우 queue에 넣는다.

Day 0 (처음 상태)

1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

Day 0의 큐에 (0, 0), (3, 5)가 담긴다.

 

Day 0의 큐의 size만큼 for문을 돌며 토마토의 상하좌우를 확인한 후 토마토들을 익히면 하루가 지나간다.

Day 1

1 -1 0 0 0 0
1 -1 0 0 0 0
0 0 0 0 -1 1
0 0 0 0 -1 1

Day 1의 큐에는 Day 0의 큐의 상하좌우의 값이 0인 경우에 해당되는 좌표인 (1, 0), (2, 5)가 담긴다. 

 

이러한 과정이 반복되고 Day 6이 된다.

Day 6

1 -1 1 1 1 1
1 -1 1 1 1 1
1 1 1 1 -1 1
1 1 1 1 -1 1

추가된 토마토들의 상하좌우에 더 이상 익힐 토마토가 없으므로 큐가 비게 되어 while문이 종료된다.

 

출력할 때 토마토 칸을 체크하는 메서드 구현

 

위의 출력을 보면 해당 조건이 존재한다.

토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

static boolean checkTomato() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 0) {
                return false;
            }
        }
    }
    return true;
}

 

토마토 칸을 돌면서 익지 않은 토마토가 존재하는 경우 false를 return 하고 그 외의 경우 true를 return 한다.

 

bfs 메서드 마무리

 

위의 bfs 메서드에서 설명하지 않고 넘어간 부분이 있다.

if (checkTomato()) return day - 1;
return -1;

 

while문이 종료된 후 토마토 칸을 체크해야 한다.

해당 함수가 true인 경우, 모든 토마토가 익은 상태이기 때문에 day - 1을 return 한다.

그 외의 경우에는 토마토가 모두 익지 못하는 상황이므로 -1을 return 한다.

 

왜 day가 아닌 day - 1을 return 할까?

위의 예시에서 Day 6일 때 queue에는 마지막으로 익은 2개의 토마토가 들어있다. 이때 모든 토마토가 익게 되지만 그를 확인하기 위해 한번 더 반복문이 돌게 된다. 실질적으로 토마토가 모두 익은 순간은 마지막 반복문이 돌기 전의 날이기 때문에 day - 1을 return 한다.

 

또한 고려해야할 출력 조건이 하나 더 있다.

저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 한다.

코드를 추가하지 않아도 0이 출력되므로 그대로 구현을 마무리한다.

 

최종 코드

 

public class BOJ_7576 {
    static int[][] board;
    static Queue<Tomato> queue;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        queue = new LinkedList<>();

        M = Integer.parseInt(st.nextToken());  // 가로
        N = Integer.parseInt(st.nextToken());  // 세로
        board = new int[N][M];

        // 토마토 칸 입력 받기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 1) {
                    queue.offer(new Tomato(i, j));
                }
            }
        }

        System.out.println(bfs());
    }

    public static int bfs() {
        // 상하좌우
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        int day = 0;
        int size = queue.size();

        while (!queue.isEmpty()) {
            for (int i = 0; i < size; i++) {
                Tomato tomato = queue.poll();

                int x = tomato.x;
                int y = tomato.y;

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

                    if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) {
                        continue;
                    }

                    if (board[nx][ny] == 0) {
                        board[nx][ny] = 1;
                        queue.offer(new Tomato(nx, ny));
                    }
                }
            }
            size = queue.size();
            day += 1;
        }

        if (checkTomato()) return day - 1;
        return -1;
    }

    static boolean checkTomato() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}