https://www.acmicpc.net/problem/7576
이 문제는 시작점이 여러 개인 bfs 유형이다. 처음에 이 문제를 마주했을 때 어떻게 익은 토마토를 큐에 한 번에 넣을 수 있을지 고민했었다.
기본 bfs 구현에서 익은 토마토를 큐에 넣어주는 부분만 달라지고 크게 달라진 부분은 없다.
이 문제의 포인트는 익은 토마토와 인접하면서 안익은 토마토를 익은 토마토로 변경해주는 부분이라고 생각한다. 그래서 따로 방문여부를 체크하는 배열을 선언하지 않았다.
탐색이 끝난 후 토마토가 모두 익었는지 익지 않았는지 판별하기 위해 따로 check() 함수를 구현하여 0인 토마토가 있으면 -1 출력, 그렇지 않으면 토마토가 익은 일 수 day를 출력하였다.
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;
static int m;
static int[][] map;
static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
static Queue<Node> queue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
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++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
bfs();
}
public static void bfs() {
queue = new LinkedList<>();
int day = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 익은 토마토라면 큐에 추가
if (map[i][j] == 1) {
queue.add(new Node(i, j, 0)); // 처음 day = 0
}
}
}
while (!queue.isEmpty()) {
Node node = queue.poll();
day = node.day;
// 상하좌우 탐색
for (int i = 0; i < 4; i++) {
int nx = node.x + dx[i];
int ny = node.y + dy[i];
// 이동할 수 있으면서
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
// 안익은 토마토라면
if (map[nx][ny] == 0) {
// 익은 토마토로 변경
map[nx][ny] = 1;
queue.add(new Node(nx, ny, day + 1));
}
}
}
}
// 탐색 종료 후 토마토가 모두 익었으면 day 출력
if (check()) {
System.out.println(day);
// 모두 익지 못하는 상황이면 -1 출력
} else {
System.out.println(-1);
}
}
// 토마토가 모두 익었는지 안익었는지 확인하는 함수
public static boolean check() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 0) {
return false;
}
}
}
return true;
}
}
// 좌표와 날짜
class Node {
int x;
int y;
int day;
public Node(int x, int y, int day) {
this.x = x;
this.y = y;
this.day = day;
}
}