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

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

7576번: 토마토

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};
        int[][] tomato = new int[N][M];

        int count = 0, days = 0;
        Queue<int[]> queue = new LinkedList<>();

        for (int n = 0; n < N; n++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
            for (int m = 0; m < M; m++) {
                tomato[n][m] = Integer.parseInt(st1.nextToken());
                if (tomato[n][m] == 1) 
                    queue.add(new int[]{n, m});
                else if (tomato[n][m] == 0) 
                    count++;
            }
        }

        while (count > 0 && !queue.isEmpty()) {
            for (int s = queue.size(); s > 0; s--) {
                int[] check = queue.poll();

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

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

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

 

1. 변수 선언 부

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};
        int[][] tomato = new int[N][M];

        int count = 0, days = 0;
        Queue<int[]> queue = new LinkedList<>();

 M ,  N  : 각각 상자의 가로 칸의 수, 세로 칸의 수를 저장할 변수

 dy ,  dx  : 익은 토마토의 상하좌우 탐색을 위한 배열

 tomato  : 토마토 정보를 담을 배열

 count  : 총 덜 익은 토마토의 수를 저장할 변수

 days  : 다 익는 데까지 걸리는 일 수를 저장할 변수

 queue  : 익은 토마토 위치를 push 할 큐

 

 

2. for 문 : 상자에 저장된 토마토들의 정보 저장

        for (int n = 0; n < N; n++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
            for (int m = 0; m < M; m++) {
                tomato[n][m] = Integer.parseInt(st1.nextToken());
                if (tomato[n][m] == 1) 
                    queue.add(new int[]{n, m});
                else if (tomato[n][m] == 0) 
                    count++;
            }
        }

- st1으로 토마토 정보를 한 줄씩 입력 받고, nextToken()을 사용하여 한 개씩 끊어 저장한다.

 if (tomato[n][m] == 1)   : 익은 토마토는 해당 좌표를 배열의 형태로 queue에 추가한다.

 else if (tomato[n][m] == 0)  : 덜 익은 토마토의 경우 count를 1만큼 증가시킨다.

 

 

3. while 문 : 토마토가 익는 데 걸리는 날 계산

        while (count > 0 && !queue.isEmpty()) {
            for (int s = queue.size(); s > 0; s--) {
                int[] check = queue.poll();

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

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

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

 

- 1)

while (count > 0 && !queue.isEmpty()) {

- count가 0 이거나 (덜 익은 토마토가 없거나), queue가 빈 경우(익은 토마토가 없는 경우) while문 종료

 

 

- 2)

for (int s = queue.size(); s > 0; s--) {
	int[] check = queue.poll();

 

- 익은 토마토가 2개 이상인 경우가 있으므로 queue를 모두 탐색하므로써 모든 익은 토마토의 상하좌우를 탐색하여야 하루가 경과한다고 볼 수 있다.

-  poll  : 큐의 가장 먼저 저장된 요소를 반환하고, 해당 요소를 큐에서 제거한다. 만약 큐가 비어있으면 null을 반환함.

        → 전날 익은 토마토에 대해서만 검사하기 위하여 한번 검사한 토마토의 좌표는 큐에서 제거

 

- 3)

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

- ny : 현재 검사할 토마토의 y좌표 + dy[k]

- nx : 현재 검사할 토마토의 x좌표 + dx[k]

  → (dx, dy)가 차례로 (0, -1) (0, 1) (-1, 0) (1, 0)으로 각각 하, 상, 좌, 우를 확인한다.

 

- 4)

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

        count--;
        tomato[ny][nx] = 1;
        queue.add(new int[]{ny, nx});
    }
}

- 상하좌우 값이 좌표 밖이거나, 해당 토마토가 0이 아닌 경우(익은 토마토 or 빈 상자) →  continue 

- 해당 칸이 안익은 토마토였을 경우

    → count 1만큼 감소 : 덜 익은 토마토 1 감소

    → 해당 칸 1로 변경 : 덜 익은 토마토가 익은 토마토로 변경됨
    → 새로 익은 토마토 queue에 추가 : 덜 익은 토마토가 익었으므로 해당 토마토의 좌표를 queue에 추가

 

 

- 5)

            days++;
        }
        System.out.println(count == 0 ? days : -1);
    }
}

- queue를 모두 탐색했을 경우 하루가 경과하였으므로 days 1만큼 증가

- while 문 종료 후 count 값이 0이면 모두 익은 토마토 이므로 days 즉, 총 걸린 일 수를 출력하고, count가 0이 아닌 경우 덜 익은 토마토가 남았다는 의미이므로 -1을 출력한다.