https://www.acmicpc.net/problem/7576
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static int[][] arr;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int day;
static Queue<Point> queue = new LinkedList<>();
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void bfs() {
while (!queue.isEmpty()) {
Point p = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || arr[nx][ny]==-1) continue;
if(arr[nx][ny] == 0){ // 아직 익지 않은 토마토라면
arr[nx][ny] = arr[p.x][p.y]+1; // 이전 토마토까지 익는데 걸린 날짜 + 1
queue.add(new Point(nx,ny));
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[m][n];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j] == 1) queue.offer(new Point(i, j)); // 익은 토마토면 큐에 넣음
}
}
bfs();
boolean flag = true;
int day = Integer.MIN_VALUE;
loop:
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(arr[i][j] == 0) { // bfs를 돌고도 익지 않은 토마토가 남아있다면
flag = false;
break loop;
}
else day = Math.max(day, arr[i][j]); // 모든 토마토가 익는데 걸린 시간은 배열 값 중에 가장 큰 값
}
}
if(!flag) System.out.println(-1);
else System.out.println(day-1); // 첫 시작 값이 1이였으므로
}
}
최소 날짜를 구해야 하므로 bfs로 푼다.
이 문제에서 포인트는 익은 토마토가 여러개 있을 때 같이 시작하여 그 주위 토마토들로 퍼져 나간다는 것인데,
그렇기 때문에 일단 익은 토마토의 좌표를 입력받아 큐에 다 집어넣고 bfs를 시작해야 한다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 1182 - 부분수열의 합 (0) | 2022.12.17 |
---|---|
[JAVA] 백준 13023번- ABCDE (0) | 2022.12.17 |
[JAVA] 백준 7562번- 나이트의 이동 (0) | 2022.12.16 |
[JAVA] 백준 2667번- 단지번호붙이기 (0) | 2022.12.16 |
[JAVA] 백준 4963번- 섬의 개수 (0) | 2022.12.15 |