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

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

728x90

https://www.acmicpc.net/problem/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 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[] cur = queue.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; 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 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[] cur = queue.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; 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[] cur = queue.poll();

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

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

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

- 3)

for (int k = 0; k < 4; k++) { int ny = cur[0] + dy[k]; int nx = cur[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을 출력한다.

728x90

from http://mingmeng030.tistory.com/196 by ccl(A) rewrite - 2021-10-06 20:01:11