[BOJ] 7576 토마토 - JAVA

1. 문제

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

7576번: 토마토

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

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

---

2. 풀이

입력

• 익은 토마토가 입력되었을 때, queue에 더한다. 

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());

int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());

int[][] tomato = new int[N][M];
Queue<int[]> queue = new LinkedList<>();

for (int i = 0; i < N; i++) {
   st = new StringTokenizer(in.readLine());
   for (int j = 0; j < M; j++) {
      tomato[i][j] = Integer.parseInt(st.nextToken());
      if (tomato[i][j] == 1) queue.offer(new int[]{i, j});
   }
}

탐색 - BFS

• 가장 최소인 날짜를 구하려면 넓이 우선 탐색이 필요하다. queue에 이미 넣은 토마토를 활용해 인접 토마토 값을 +1 해 가면서 다음 위치를 넣는다.
• 따라서 범위 체크와 동시에 0이 아닌지를(depth로 토마토상자값을 덮어씌울 것이므로) 체크해야 한다.
• depth를 저장할 때는 7번 줄처럼 -1을 해야 한다. 입력받을 때 이미 익어있는(1인) 토마토가 문제상으로 0일 만에 익기 때문에 값을 그대로 depth에 저장하다 보면 첫 번째 토마토가 익는 데 하루가 걸린다고 여기는 결과가 나온다.

int[][] deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int depth = 0;
int[] v;
while (!queue.isEmpty()) {
   v = queue.poll();
   depth = Math.max(depth, tomato[v[0]][v[1]]-1);

   for (int d = 0; d < 4; d++) {
      int ny = v[0] + deltas[d][0];
      int nx = v[1] + deltas[d][1];
      if (ny < 0 || ny >= N || nx < 0 || nx >= M || tomato[ny][nx] != 0) continue;
      tomato[ny][nx] = tomato[v[0]][v[1]] + 1;
      queue.offer(new int[]{ny, nx});
   }
}

출력

• 하나씩 돌아가면서 0인 토마토가 있는지 확인한다. 있다면 -1을 출력하고 바로 메인 함수를 끝낸다.
• 위에서 끝나지 않았다면 depth를 출력한다.

for (int i = 0; i < N; i++) {
   for (int j = 0; j < M; j++) {
      if (tomato[i][j] == 0) {
         System.out.println(-1);
         return;
      }
   }
}

System.out.println(depth);

---

3. 결과

전형적인 BFS문제였다.