- Today
- Total
hye-log
[백준]7576번 토마토(JAVA) 본문
0. 문제 링크
https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
1. 문제 설명
1) M*N 직사각형의 상자에 토마토 보관
2) 하루가 지나면 익은 토마토의 인접한 곳(왼쪽, 오른쪽, 앞, 뒤)에 익지 않은 토마토가 익음
3) 토마토가 며칠이 지나면 다 익는지 최소 일수 구하기
4) 저장될 떄부터 모든 토마토가 익어있는 상태면 0, 모두 익지 못하는 상태면 -1 출력
2. 입출력
// input
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
// output
8
3. 코드
import java.awt.Point;
import java.io.*;
import java.util.*;
public class b7576 {
static int[] dr = {0, 0, -1, 1};
static int[] dc = {-1, 1, 0, 0};
private static int M;
private static int N;
private static int[][] map;
private static Queue<Point> q = new ArrayDeque<Point>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// step 1. 입력
M = Integer.parseInt(st.nextToken()); // 가로
N = Integer.parseInt(st.nextToken()); // 세로
map = new int[N][M]; // 상자
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
// 1: 익은, 0: 익지 않은, -1: 토마토 없는
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int ans = 0;
// step 2. 토마토 익히기
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 1) { // 익은 토마토이면 퍼뜨려야 함
q.offer(new Point(i, j)); // 큐에 넣기
}
}
}
bfs(); // 토마토 퍼뜨리기
// step 3. 안 익은 토마토가 있는지 확인
int day = 0; // 얼마나 지났는지
boolean ingTomato = false; // 안 익은 토마토(0) 여부
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0) { // 안 익은 토마토가 있다면
ingTomato = true;
break;
} else { // 익은 토마토가 있으면 언제 익었는지
day = Math.max(day, map[i][j]);
}
}
}
// step 4. 토마토가 모두 익었는지에 따라 정답 결정
if(ingTomato) { // 토마토가 모두 익지 못하는 상황 (안 익은 토마토가 있음)
ans = -1;
} else { // 토마토가 모두 익은 상황
ans = day - 1; // 익은 토마토가 1부터 시작했으므로 1 빼기. day가 0이면 저장될 때부터 모두 익어 있는 상태
}
System.out.println(ans);
}
private static void bfs() {
while(!q.isEmpty()) {
Point p = q.poll();
for (int d = 0; d < 4; d++) {
int nr = p.x + dr[d];
int nc = p.y + dc[d];
if(nr >= 0 && nr < N && nc >= 0 && nc < M) {
if(map[nr][nc] == 0) { // 익지 않은 토마토이면 익히기
map[nr][nc] = map[p.x][p.y] + 1; // 토마토 익히기
q.add(new Point(nr, nc));
}
}
}
}
}
}
실행 결과
4. 회고
1) 처음에 모든 배열을 탐색하는 bfs로 풀었는데 시간 초과가 발생함
2) bfs는 갈림길이 있어도 자식 노드를 끝까지 탐색하기 때문에 이 성질을 이용하여 토마토가 익는 최소 일수를 구함
- 배열을 탐색하면서 익은 토마토를 큐에 넣음
- 큐에서 요소를 하나씩 꺼내며 사방 탐색을 진행함
- 안 익은 토마토가 있으면 토마토를 익히고 현재 토마토 값에 1을 더함 (하루씩 지나면서 퍼지므로)
3) 배열을 다시 탐색해서 안 익은 토마토가 있다면 ingTomato를 false로, 익은 토마토 중에서 최대값을 구해서 최소 일수에 저장
4) ingTomato가 true이면 -1, false이면 day -1 로 출력(day의 시작이 익은 토마토인 1부터 시작했기 때문)
5. Github
https://github.com/iihye/Algorithm/blob/main/Baekjoon/b7576.java
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준]16935 배열 돌리기3(JAVA) (0) | 2023.08.10 |
---|---|
[백준]16926번 배열 돌리기1(JAVA) (0) | 2023.08.10 |
[백준]4963번 섬의 개수(JAVA) (0) | 2023.08.10 |
[백준]1012번 유기농 배추(JAVA) (0) | 2023.08.09 |
[백준]1158번 요세푸스 문제(JAVA) (0) | 2023.08.08 |