[백준] 7576번: 토마토 - JAVA

🔗 문제 링크

BOJ 7576번: 토마토

7576번: 토마토

 

📝 풀이 과정

익은 토마토가 주변의 앞, 뒤, 왼쪽, 오른쪽 4방향의 안익은 토마토를 익게 만드는 총 일수를 구하는 문제이다. 전형적인 BFS 문제의 구조를 띄고 있다.

 

처음 입력을 받으며 익은 토마토는 Queue에 넣는다.나의 경우 Queue에 int[] 배열로 토마토의 위치를 저장하였다.

마지막에 안익은 토마토가 존재할 경우 -1을 출력하는 조건 존재하기 때문에 이를 처리하기 위해 안익은 토마토가 등장할 경우 숫자를 카운트 해준다.

 

Queue에서 하나씩 poll하며 4방향 탐색을 하며, 익지 않은 토마토(0)가 존재할 경우 익은 토마토(1)로 변경한다. 이렇게 하면 visit처리를 해주지 않고도 다시 탐색을 하지 않도록 막을 수 있다.

 

 

이 문제에서는 토마토가 모두 익게 되는 최소 날짜를 구해야 하는데 한 Queue에 들어가 모두 비워지는 경우가 하루이다.
위와 같이 Queue에 몇 개의 토마토가 들어갔던 Queue가 모두 비워지는 경우는 하루이다.

 

따라서, Queue에 값을 추가할 때, 다른 Queue나 List에 값을 넣은 다음 Queue가 비워졌을 때 기존의 Queue에 모두 추가해주는 방법도 있다. 그리고, for문을 통해 Queue의 size만큼 돌게 되면 하루만큼 경과하기 때문에 이러한 방식으로 문제를 풀어보았다.

 

💻 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dy = { -1, 1, 0, 0 };
        int[] dx = { 0, 0, -1, 1 };
        int M = sc.nextInt(), N = sc.nextInt();

        int[][] tomato = new int[N][M];
        int cnt = 0, days = 0;
        Queue<int[]> que = new LinkedList<>();

        for (int n = 0; n < N; n++)
            for (int m = 0; m < M; m++) {
                tomato[n][m] = sc.nextInt();
                if (tomato[n][m] == 1)
                    que.add(new int[] { n, m });
                else if (tomato[n][m] == 0)
                    cnt++;
            }

        while (cnt > 0 && !que.isEmpty()) {
            for (int s = que.size(); s > 0; s--) {
                int[] cur = que.poll();

                for (int k = 0; k < 4; k++) {
                    int ny = cur[0] + dy[k];
                    int nx = cur[1] + dx[k];

                    if (ny < 0 || nx < 0 || ny >= N || nx >= M || tomato[ny][nx] != 0)
                        continue;

                    cnt--;
                    tomato[ny][nx] = 1;
                    que.add(new int[] { ny, nx });
                }
            }
            days++;
        }
        System.out.println(cnt == 0 ? days : -1);

    }
}

 

📊 제출 결과